Потенциал Образовательный журнал
для старшеклассников и учителей

<< К разделам
Информатика
Алгоритмы
Теория информации
Теория программирования
Все статьи
Журнал
Подписка
Интернет-Журнал «Потенциал» External link mark
Авторам
Печатные номера
Полезные сайты
ЗФТШ External link mark
МЦНМО External link mark
Журнал "Квант" External link mark
"Открытый Колледж" External link mark
Союз образовательных сайтов External link mark
Интернет-портал "Абитуриент" External link mark
Другие ссылки...

WOlist.ru - каталог качественных сайтов Рунета Союз образовательных сайтов Rambler's Top100 Портал ВСЕОБУЧ. Все образование Москвы и регионов РФ.

Главная Подписка Архив Авторы Фотоальбом Подготовка в вуз Магазин

Задача "Кафе" с московской командной олимпиады

Ворожцов А.В.


14 ноября прошла командная московская олимпиада школьников. Мы решили опубликовать и разобрать некоторые задачи с этой олимпиады. Начнём с задачи "Кафе".

Ссылки

Формулировка

Меню

  • Имя входного файла: b.in
  • Имя выходного файла: b.out
  • Максимальное время работы на одном тесте: 2 секунды
  • Максимальный объем используемой памяти: 64 мегабайта

Около Петиного университета недавно открылось новое кафе, в котором действует следующая система скидок: при каждой покупке более чем на 100 рублей покупатель получает купон, дающий право на один бесплатный обед.

Однажды Пете на глаза попался прейскурант на ближайшие N дней. Внимательно его изучив, он решил, что будет обедать в этом кафе все N дней, причем каждый день он будет покупать в кафе ровно один обед. Однако стипендия у Пети небольшая, и поэтому он хочет по максимуму использовать предоставляемую систему скидок так, чтобы его суммарные затраты были минимальны. Требуется найти минимально возможную суммарную стоимость обедов и номера дней, в которые Пете следует воспользоваться купонами.

Формат входных данных

В первой строке входного файла записано целое число N ( 0 ≤ N ≤ 100). В каждой из последующих N строк записано одно целое число, обозначающее стоимость обеда в рублях на соответствующий день. Стоимость — неотрицательное целое число, не превосходящее 300.

Формат выходных данных

В первой строке выведите минимальную возможную суммарную стоимость обедов. Во второй строке выведите два числа K1 и K2 — количество купонов, которые останутся неиспользованными у Пети после этих N дней и количество использованных им купонов соответственно.

В последующих K2 строках выведите в возрастающем порядке номера дней, когда Пете следует воспользоваться купонами. Если существует несколько решений с минимальной суммарной стоимостью, то выведите то из них, в котором значение K1 максимально (на случай, если Петя когда-нибудь ещё решит заглянуть в это кафе). Если таких решений несколько, выведите любое из них.

Пример

b.in b.out
5 35 40 101 59 63 229 0 1 5

Разбор задачи

В приведённом выше примере N = 5. Обед в первый день стоит 35 рублей, во второй – 40 рублей, и т.д. В первые три дня Петя вынужден платить, так как у него нет купонов. Но в третий день он получает один купон, так как платит 101 рубль за обед. Он может истратить этот купон на следующий день. Но экономичнее израсходовать его на пятый день. Суммарные затраты Пети в указанном примере составили

35+40+101+53 = 229 рублей.

Итак, нам даны стоимости обедов и нам нужно решить, за какие обеды мы платим рублями, а какие получаем за купоны. Купоны приобретаются в те дни, когда мы платим деньгами за обед более, чем 100 рублей.

Задача решается методом динамического программирования. Это значит, что вместо одной задачи, мы рассмотрим целый класс задач, начнём решать простые задачи из этого класса и постепенно дойдём до нужной нам задачи.

Определим функцию:

Money(d, k) = минимальное число денег, которые можно потратить за первые d дней и иметь в результате на руках k или больше купонов.

Вычислить эту функцию при всевозможных параметрах d и k — и есть наш класс задач. Нас интересует только значение Money(N, 0), то есть минимальное количество денег, которые Петя может потратить за N дней и иметь в конце на руках 0 или больше купонов. Но чтобы вычислить это значение, нам придется вычислить Money(d, k) при различных значениях параметров.

Обозначим цену обеда в d-й день через Price(d). Несложно понять, что

  • Money(1, K) = undef , если K > 1,
  • Money(1, 0) = Price(1) и Money(1, 0) = undef , если Price(1) ≤ 100,
  • Money(1, 0) = Money(1, 1) = Price(1) , если Price(1) > 100.

Где undef обозначает "неопределенность", то есть нет возможности иметь столько купонов в этот день. Можно считать, что undef = +∞.

Естественно рассматривать Money как двемерный массив или таблицу. Указанные выше правила позволяют вычислить первую строчку этой таблицы.

Осталось, двигаясь змейкой по строчкам, вычислить значения остальных её элементов. Внешний цикл будет по переменной D (строчки), а внутренний по переменной K (столбцы). Вычислять будем пользуясь рекурентной формулой:

  • Money(D,K) = MIN( Money(D-1, K) + Price(D) , Money(D-1, K + 1) ), если Price(D) ≤ 100,
  • Money(D,K) = MIN( Money(D-1, K-1) + Price(D) , Money(D-1, K) ), если Price(D) > 100.

Эти соотношения выражают число Money(D,K), стоящее в строчке D, через число стоящее над ним в предыдущей строчке, а также через числа, стоящие в предыдущей строчке в двух соседних столбцах.

Формулы, которые выражают значение некоторой величины через значения этой величины при других значениях параметров (обычно меньших), называются рекуррентными формулами.

Указанная рекуррентная формула позволяет последовательно, строчка за строчкой вычислить всю таблицу Money. Таблица будет треугольной, так как Money(D, K)=undef при K > D.

По таблице можно восстановить, в какие дни следует платить купон, а в какие — тратить. Разберитесь в этом самостоятельно.

Отметим важный момент. В задаче требуется, чтобы мы минимизировали количество потраченых денег и среди оптимальных решений выбрали то, в котором число оставшихся на руках купонов максимально.

То есть нужно найти максимальное k, такое что Money(N, k ) = Money(N, 0), это и будет искомое K1.

Покажите, что иметь в конце на руках более одного купона не экономично, то есть K1=0 или 1.

Постройте вручную таблицу Money для входа N=5, Price={101,102,50,90,103}.

Решите следующую задачу.

У Пети есть определенное количество денег. Нужно потратить их (или часть из них) и иметь в конце как можно больше купонов.


© Журнал "Потенциал", 2005-2017. Все права защищены. Воспроизведение материалов сайта и журнала "Потенциал" в любом виде, полностью или частично, допускается только с письменного разрешения редакции.
Отзывы и пожелания шлите почтой.
Подготовка к ЕГЭ
ЕГЭ по математике
login