18

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

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

В ответе записывают минимальную сумму, затем максимальную сумму.

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

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

Условие

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

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

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

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

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

Используют только один показатель и не вычисляют отдельно минимум и максимум.

Разрешают движение вверх или влево, хотя Робот может двигаться только вправо и вниз.

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

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

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

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