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

Разделы > Неотсортированные > задача:


Копилка

Задачи раздела

• Длинный НОД
• Ездец
• За решеткой
• Забавная игра
• Запаковка
• Змейка
• Игра в числа
• КВН
• Копилка
• Коррекция кода
• Лесенки
• Макс и A0
• Макс и выдача багажа
• Макс и дуэль танков
• Макс и офисная улица
• Макс и перемешанные фотографии
• Макс и розыгрыш приза

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

Если у вас есть предложения или пожелания по работе 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