18

Ответ: Максимальная и минимальная суммы

ЕГЭ · Информатика · Задание 18 · Динамическое программирование
ПовышеннаяФИПИ6999A7Развёрнутое решение≈ 10 минут
Что должно получиться

В приложенной электронной таблице укажите максимальную сумму, затем минимальную.

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

Условие

Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо» Робот перемещается в соседнюю правую клетку, по команде «вниз» — в соседнюю нижнюю. При попытке пересечь внутренние границы или границы квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. Исходные данные представляют собой электронную таблицу размером $N \times N$, каждая ячейка которой соответствует клетке квадрата.

Открыть задачу и решить самому

Где здесь ошибаются

Не учитывать монеты в начальной или конечной клетке.

Использовать минимум для обеих таблиц или максимум для обеих таблиц.

Разрешить перемещения вверх или влево.

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

Откуда взялся этот ответРазбор разложен на 4 шага: видно каждое преобразование и где теряется балл.
Открыть решение

Ответ к заданию 18 ЕГЭ, информатика

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

Задача из темы «Динамическое программирование»: в ней 72 задачи — у каждой есть ответ и разбор по шагам. Регистрация не нужна.