Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра --> Задача о рюкзаке
---> 2 задач <---
Источники --> Командные олимпиады --> Московская командная олимпиада --> 9-11 классы
    2003(8 задач)
    2004(9 задач)
    2005(10 задач)
    2006(10 задач)
    2007(19 задач)
    2008(19 задач)
    2009(18 задач)
    2010(18 задач)
    2011(18 задач)
    2012(19 задач)
    2013(19 задач)
    2014(20 задач)
    2015(21 задач)
    2016(20 задач)
Страница: 1 Отображать по:
#1623
Пицца
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более \(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 (минус один).

Примеры
Входные данные
10 17 25
5
2 7 5 3 7
Выходные данные
26
3 1 2 5
#1633
Пицца
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более \(C\) рублей, доставка является бесплатной, при заказе на \(C\) рублей и меньше доставка стоит \(B\) рублей. Вы уже выбрали товара стоимостью \(A\) рублей. В наличии имеются еще \(N\) товаров стоимостью \(d_1, ..., d_N\) рублей, каждый в единственном экземпляре. Их также можно включить в заказ. Как потратить меньше всего денег и получить на дом уже выбранный товар стоимостью \(A\) рублей?

Входные данные

Вводятся сначала числа \(A, B, C, N,\) а затем \(N\) чисел \(d_1, ..., d_N\). Все числа целые, \(1 \le A \le 1000, 1 \le B ≤ 1000, 1 \le C \le 1000, 0 \le N \le 1000, 1 \le di \le 1 000 000\).

Выходные данные

Выведите единственное число – суммарное количество денег, которое придется потратить.

Примечание
В первом примере экономнее всего докупить 1, 2 и 5 товары. Во втором ничего докупать не надо, ведь доставка уже стала бесплатной. В третьем дешевле всего заплатить за доставку самому.
Примеры
Входные данные
10 17 25
5
2 7 5 3 7
Выходные данные
26
Входные данные
100 1 50
5
5 2 4 3 1
Выходные данные
100
Входные данные
10 14 25
5
2 7 5 3 7
Выходные данные
24
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест