Задача 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