Максимум и минимум монет

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

ВысокаяФИПИF7EDCCКороткий ответ≈ 10 минут

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

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

F7EDCC.zipАрхив ZIP · 34 КБВнутри: 1_18.xls, 1_18.xlsx, 1_18.ods

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

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

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

Квадрат разлинован на 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

Заполните две таблицы динамического программирования с учётом стен. В правой нижней клетке первой таблицы получится максимальная сумма, а второй — минимальная.

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

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

ПредыдущаяМаксимальная и минимальная суммаСледующаяВычисление рекурсивной функции

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