Начало
ЗадачиПодразделы
Другие разделы
| STL |
| Антагонистические игры |
| Геометрия |
| Графы |
| Дихотомия |
| Длинная арифметика |
| Комбинаторика |
| Неклассифицированные |
| Основы |
| Перебор |
| Поиск в глубину |
| Поиск в ширину |
| Последовательности |
| Сортировка |
| Теория чисел |
Дата и время
17/11/2024 09:21:02
Динамическое программирование
And Then There Was One Broken Sword: потерянный файл Decoding Morse Sequences SMS Бросание кубика Витрина Возрастающая подпоследовательность Гангстеры Головоломка умножения Зоопарк Копилка Кубический метр Маршрут Палиндром Разложение на простые слагаемые Скобки (3) Скобки (4) Сообщение Строки Фибоначчи
Копилка
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 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) |
| 10/07/2024 | Лето 2024-8 простые (B) |
Ограничения: время – 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.
