Максимальная и минимальная сумма

ЕГЭ · Информатика · Задание 18 · Динамическое программирование

ВысокаяФИПИE60642Развёрнутое решение≈ 10 минут

Квадрат разлинован на $N \times N$ клеток, где $1 < N < 30$. Исполнитель Робот перемещается из левой верхней клетки в правую нижнюю, выполняя команды «вправо» и «вниз». Между соседними клетками могут находиться внутренние стены, через которые Робот пройти не может. В каждой клетке лежит монета достоинством от 1 до 100; посетив клетку, Робот забирает монету, в том числе в начальной и конечной клетках.

Файл к заданию

E60642.zipАрхив ZIP · 33 КБВнутри: 2_18.xlsx, 2_18.ods, 2_18.xls

Используя приложенный файл с электронной таблицей, определите максимальную и минимальную денежные суммы, которые может собрать Робот. В ответе укажите сначала максимальную сумму, затем минимальную.

Условие как в банке ФИПИ — открыть и сверить

Впишите правильный ответ.

Задание выполняется с использованием прилагаемых
файлов.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз $-$
в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

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

Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

Пример входных данных:

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

Ответ

Это задание с развёрнутым решением: ответом считается запись хода решения, а не строка. Напишите решение на бумаге и сравните с разбором — там каждый шаг с обоснованием.

Открыть разбор

3 уровня: от лёгкого толчка до почти готового решения. Следующий открывается, когда прочитан предыдущий, — чтобы не перепрыгнуть сразу к ответу.

1Мягкая — с чего смотретьуровень 1 из 3

Для каждой клетки рассмотрите все допустимые пути, которыми Робот может в неё попасть.

2Наводящая — какие числа считатьуровень 2 из 3

Храните для каждой клетки две величины: максимальную и минимальную сумму монет на пути из начальной клетки.

3Прямая — фактически решениеуровень 3 из 3

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

Всё равно не складывается?Полное решение с обоснованием каждого шага — на отдельной странице.

Открыть решение

ПредыдущаяМаршрут Робота по клеткамСледующаяМинимальная и максимальная сумма

Задание 18 ЕГЭ, информатика