Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1773. Пицца
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 25/06/2012 | Лето 2012 - дорешивание ( 6H) |
| 04/07/2012 | Лето 2012 - 6 (H) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов,
сделавших заказ на сумму более `C` рублей, доставка является бесплатной, при заказе на `C` рублей и
меньше доставка стоит `B` рублей.
Вы уже выбрали товар, стоимостью `A` рублей. В наличии имеются еще `N` товаров
стоимостью `d_1,\ …,\ d_N` рублей, каждый в единственном экземпляре. Их также можно включить в заказ.
Как потратить меньше всего денег и получить на дом уже выбранный товар в `A` рублей?
Сначала вводятся числа `A`, `B`, `C`, `N`, а затем `N` чисел `d_1,\ …,\ d_N`.
Все числа целые, `1\ ≤\ A\ ≤\ 1000`, `1\ ≤\ B\ ≤\ 1000`, `1\ ≤\ C\ ≤\ 1000`, `0\ ≤\ N\ ≤\ 1000`, `1 ≤ d_i ≤\ 1\ 000\ 000`.
Выведите сначала суммарное количество денег, которое придется потратить.
Если при этом вы планируете сделать дополнительный заказ c расчетом на
бесплатную доставку, то далее выведите количество
этих товаров и их номера в возрастающем порядке. Если же Вы будете
оплачивать доставку сами, то далее выведите одно число `–1` (минус один).
Пример ввода 1
10 17 25 5 2 7 5 3 7
Пример вывода 1
26 3 1 2 5
Пример ввода 2
100 1 50 5 5 2 4 3 1
Пример вывода 2
100 0
Пример ввода 3
10 14 25 5 2 7 5 3 7
Пример вывода 3
24 -1
Источник: Московская командная олимпиада школьников по программированию, 2009/10 учебный год
