ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66639
Темы:    [ Теория алгоритмов (прочее) ]
[ Задачи на максимум и минимум (прочее) ]
Сложность: 3
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Марина купила тур в Банановую страну с 5 по 22 октября. Ввозить и вывозить бананы через границу запрещено. Банановый король в начале каждого месяца издаёт указ о ценах. Цена одного банана в местной валюте на нужные числа октября приведена в таблице:

$\,$5 $\,$6 $\,$7 $\,$8 $\,$9 10 11 12 13 14 15 16 17 18 19 20 21 22
8,1 $\,$8 $\,$7 8,1 $\,$9 $\,$8 8,1 7,2 $\,$7 $\,$8 $\,$9 8,1 $\,$9 $\,$8 $\,$9 8,2 $\,$7 7,1

Марина хочет ежедневно съедать по одному банану. Она любит только зелёные бананы, поэтому согласна съесть банан только в течение 4 дней после покупки. Например, банан, купленный 5 октября, Марина согласна съесть 5, 6, 7 или 8 октября. Марина может запасаться бананами, когда они подешевле.

В какие дни по сколько бананов надо покупать Марине, чтобы потратить как можно меньше денег?


Решение

Чтобы решить задачу, достаточно правильно на неё посмотреть. Вместо того, чтобы думать, сколько бананов покупать в каждый день, давайте для каждого дня выберем, в какой из дней купить банан! Для этого надо выбрать самую низкую цену из четырёх: текущего дня и трёх предыдущих (если предыдущих дней меньше трёх, то смотрим только на те, что есть).

Для каждого дня на диаграмме ниже стрелкой указана самая низкая цена из доступных. Соответственно, в каждый из дней следует купить столько бананов, сколько стрелок указывают на цену под этим днём.

Получаем ответ:

$\,$5$\,$ $\,$6$\,$ $\,$7$\,$ $\,$8$\,$ $\,$9$\,$ 10 11 12 13 14 15 16 17 18 19 20 21 22
$\,$1 $\,$1 $\,$4 $\,$0 $\,$0 $\,$1 $\,$0 $\,$1 $\,$4 $\,$1 $\,$0 $\,$0 $\,$0 $\,$3 $\,$0 $\,$0 $\,$2 $\,$0


Ответ

В дни с 5 по 22 октября нужно купить, соответственно, 1, 1, 4, 0, 0, 1, 0, 1, 4, 1, 0, 0, 0, 3, 0, 0, 2, 0 бананов.

Источники и прецеденты использования

олимпиада
Название Турнир им.Ломоносова
номер/год
Год 2020
задача
Номер 7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .