Задача 66639
|
|
 |
Условие
Марина купила тур в Банановую страну с 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 |
