РУҚА
18

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

ЕГЭ · Информатика · Задание 18 · Динамическое программирование
ВысокаяФИПИ10B556Короткий ответ≈ 10 минут
Правильный ответ

Численные значения невозможно определить без содержимого прилагаемой электронной таблицы.

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

В бланк: число или слово без единиц измерения; дробную часть отделяйте запятой.

Условие

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

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

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

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

Разрешают переход через внутреннюю стену.

Ищут минимум и максимум только в правой нижней клетке, хотя конечных клеток может быть несколько.

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

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

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

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