Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
41. Копилка
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 3H) |
| 07/07/2006 | Лето 2006 - 3 (H) |
| 19/11/2010 | Занятие 10 (A) |
| 10/10/2013 | Занятие 6 для продолжающих (A) |
| 08/07/2019 | Лето 2019 - 4 (E) |
| 07/04/2022 | «Базовая олимпиадная подготовка» (second level) - Одномерная динамика (проводит novink) (B) |
| 02/03/2023 | Базовый уровень: динамическое программирование 2 (проводит BOGAT) (D) |
| 12/07/2023 | Лето 2023-8 простые (B) |
| 05/03/2024 | Динамическое программирование 2 (проводит BOGAT) (D) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Задан вес `E` пустой копилки и вес `F` копилки с монетами. В копилке могут находиться монеты `N` видов, для каждого вида известна ценность `P_i` и вес `W_i` одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Ограничения: `1\ ≤\ E\ ≤\ F\ ≤\ 10\ 000`, `1\ ≤\ N\ ≤\ 500`, `1\ ≤\ P_i\ ≤\ 50\ 000`, `1\ ≤\ "Wi"\ ≤\ 10\ 000`, все числа целые.
Ввод
В первой строке находятся числа `E` и `F`, во второй – число `N`, в следующих `N` строках – по два числа, `P_i` и `W_i`.
Вывод
Выводятся два числа через пробел – минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, – вывести "This is impossible.".
Пример ввода 1
1000 1100 2 1 1 5 2
Пример вывода 1
100 250
Пример ввода 2
1000 1010 2 6 3 2 2
Пример вывода 2
10 16
Пример ввода 3
1000 2000 1 10 3
Пример вывода 3
This is impossible.
