ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Фёдор Меньшиков. Тренировки > задача:


03C. Копилка

Задачи сборника

• 02A. Простые числа (2)
• 02B. Перестановки
• 02C. Маршрут
• 02D. z14
• 02E. Длинная сумма
• 02F. Спираль
• 03A. Разложение на простые множ...
• 03B. Перестановки (2)
• 03C. Копилка
• 03D. Открытка и конверт
• 03E. Длинное произведение
• 03F. Змейка
• 04A. Совершенные числа
• 04B. Разложение на слагаемые
• 04C. Гангстеры
• 04D. Площадь многоугольника
• 04E. Деление длинного числа на к...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Фёдор Меньшиков, ВГПУ. Сложность Гамма

Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность Pi и вес Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Ввод
В первой строке находятся числа E и F, во второй - число N, в следующих N строках - по два числа, Pi и Wi.
Вывод
Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".
Ограничения
1 ≤ EF ≤ 10 000; 1 ≤ N ≤ 500; 1 ≤ Pi ≤ 50 000; 1 ≤ Wi ≤ 10 000.

Ввод 1 Ввод 2 Ввод 3
1000 1100
2
1 1
5 2
1000 1010
2
6 3
2 2
1000 2000
1
10 3
Вывод 1 Вывод 2 Вывод 3
100 250
10 16
This is impossible.

Для отправки решений необходимо выполнить вход.

www.contester.ru