Задание 18 ЕГЭ по информатике: робот-сборщик монет — алгоритм решения

Что проверяет задание

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

• понимание ограничений движения исполнителя (только «вправо» и «вниз», разрушение при выходе за границу);
• умение построить рекуррентное соотношение для максимума и минимума суммы на пути;
• умение реализовать это соотношение в электронной таблице или программе, потому что вручную обработать сетку размером до $16\times16$ нереально.

Задание относится к «файловым» — данные даются в приложенном документе (таблица с числами), и без табличного процессора или скрипта его не решить за отведённое время.

Как выглядит формулировка и сколько баллов

Стандартная формулировка: квадрат разлинован на $N \times N$ клеток, где $1 < N < 17$. В каждой клетке лежит монета достоинством от 1 до 100. Робот стартует в левой верхней клетке, движется только вправо или вниз и финиширует в правой нижней клетке, собирая монеты со всех посещённых клеток, включая начальную и конечную. Нужно найти максимальную и минимальную сумму, которую может собрать Робот.

Особенности оформления ответа:

• ответ — два числа, записанные подряд без пробелов и разделителей;
• порядок фиксирован: сначала максимальная сумма, затем минимальная;
• данные находятся в прикреплённом файле (таблица), а не в тексте условия;
• задание оценивается в 1 первичный балл, засчитывается только точное совпадение ответа целиком (обе цифры сразу).

Что нужно знать

• Число клеток в квадрате — $N^2$, а число шагов Робота от старта до финиша всегда равно $2N-2$, число посещённых клеток — $2N-1$.
• Число различных маршрутов из левого верхнего угла в правый нижний равно $\binom{2N-2}{N-1}$ — это биномиальный коэффициент, который растёт очень быстро (уже при $N=16$ счёт идёт на сотни миллионов маршрутов), поэтому перебор всех путей вручную или простым циклом невозможен.
• Основная идея — принцип оптимальности динамического программирования: лучший (или худший) путь до клетки $(i,j)$ строится только из лучшего пути до соседа сверху $(i-1,j)$ или соседа слева $(i,j-1)$.
• Рекуррентные формулы для максимальной суммы $M_{max}(i,j)$ и минимальной $M_{min}(i,j)$: $$M_{max}(i,j) = a_{ij} + \max\big(M_{max}(i-1,j),\ M_{max}(i,j-1)\big)$$ $$M_{min}(i,j) = a_{ij} + \min\big(M_{min}(i-1,j),\ M_{min}(i,j-1)\big)$$ где $a_{ij}$ — значение монеты в клетке $(i,j)$.
• Граничные условия: первая строка и первый столбец имеют только один возможный путь — накопительную сумму: $$M_{max}(1,j)=M_{min}(1,j)=\sum_{k=1}^{j} a_{1k}, \qquad M_{max}(i,1)=M_{min}(i,1)=\sum_{k=1}^{i} a_{k1}$$
• Ответ — это $M_{max}(N,N)$ и $M_{min}(N,N)$, записанные подряд.
• Пригодятся базовые навыки табличного процессора: относительные и абсолютные ссылки (знак $), функции МАКС()/MAX() и МИН()/MIN(), автозаполнение формул протягиванием.

Методы решения

1. Динамическое программирование «по клеткам» (основной метод). Строится не одна, а две вспомогательные таблицы того же размера — для максимума и для минимума. Мини-пример: пусть в клетке $(2,2)$ лежит монета $a=1$, а до соседей уже посчитано $M_{max}(1,2)=10$ и $M_{max}(2,1)=8$. Тогда $M_{max}(2,2)=1+\max(10,8)=11$.

2. Работа в электронной таблице. В отдельный лист копируется исходная сетка, рядом строятся две таблицы-двойники. В верхнюю левую ячейку каждой копируется значение из исходной таблицы, в первую строку и столбец — накопительные суммы, а во все остальные ячейки протягивается формула вида =A1+МАКС(B0;A0) (с соответствующими абсолютными и относительными ссылками). Итог считывается из правого нижнего угла каждой таблицы.

3. Программный способ. Если удобнее писать код (Python, Pascal, школьный алгоритмический язык), матрица считывается из файла в двумерный массив, затем заполняются два массива dp_max и dp_min по тем же рекуррентным формулам, ответ — значения в последней ячейке обоих массивов.

4. Комбинаторная проверка целесообразности метода. Перед решением полезно прикинуть число маршрутов по формуле $\binom{2N-2}{N-1}$. Например, для $N=4$ число маршрутов $\binom{6}{3}=20$ — перебрать можно вручную. Для $N=16$ получается $\binom{30}{15}\approx 1.5\cdot10^8$ — перебор исключён, только динамическое программирование.

5. Ручная проверка на маленьких сетках. Перед тем как доверять формулам в большой таблице, стоит вручную решить маленький пример (например $3\times3$) и сравнить результат с полным перебором путей — это позволяет обнаружить ошибку в формуле ещё до применения её к большому файлу.

Алгоритм решения по шагам

1. Открыть приложенный файл и определить размер квадрата $N$ (число строк или столбцов таблицы).
2. Скопировать исходную таблицу монет в два места на листе — будущие таблицы $M_{max}$ и $M_{min}$.
3. В верхнюю левую ячейку обеих копий вписать значение $a_{11}$.
4. Заполнить первую строку и первый столбец накопительными суммами (единственный путь).
5. Во все остальные ячейки таблицы $M_{max}$ ввести формулу $a_{ij}+\max(\text{сосед сверху};\text{сосед слева})$ и протянуть её на весь диапазон.
6. Аналогично заполнить таблицу $M_{min}$, заменив функцию максимума на минимум.
7. Считать значения из правых нижних ячеек обеих таблиц — это максимальная и минимальная суммы.
8. Записать ответ как две цифры подряд: сначала максимум, затем минимум, без пробелов и знаков.

Разбор примеров

Чтобы увидеть механику целиком, разберём компактную сетку $3\times3$ — та же логика применяется и к настоящим файлам размером до $16\times16$, просто в них таблицы крупнее и заполняются протягиванием формул.

Пусть таблица монет такая: $$\begin{pmatrix} 3 & 7 & 2 \\ 5 & 1 & 8 \\ 4 & 6 & 3 \end{pmatrix}$$

Шаг 1. Таблица максимумов. Первая строка и столбец — накопительные суммы: $M_{max}(1,1)=3$, $M_{max}(1,2)=10$, $M_{max}(1,3)=12$; $M_{max}(2,1)=8$, $M_{max}(3,1)=12$.

Далее по формуле $M_{max}(i,j)=a_{ij}+\max(верх,лево)$: $M_{max}(2,2)=1+\max(10,8)=11$; $M_{max}(2,3)=8+\max(12,11)=20$; $M_{max}(3,2)=6+\max(11,12)=18$; $M_{max}(3,3)=3+\max(20,18)=23$.

Максимальная сумма — 23.

Шаг 2. Таблица минимумов. Первая строка и столбец совпадают с предыдущими (путь единственный): 3, 10, 12 и 8, 12.

$M_{min}(2,2)=1+\min(10,8)=9$; $M_{min}(2,3)=8+\min(12,9)=17$; $M_{min}(3,2)=6+\min(9,12)=15$; $M_{min}(3,3)=3+\min(17,15)=18$.

Минимальная сумма — 18. Итоговый ответ для этой сетки: 2318.

Проверка полным перебором (для $3\times3$ путей всего 6) подтверждает результат: путь «вправо-вправо-вниз-вниз» даёт $3+7+2+8+3=23$ (максимум), а путь «вниз-вправо-вниз-вправо» даёт $3+5+1+6+3=18$ (минимум) — формулы работают верно.

В реальных заданиях banка (условно назовём их Пример 1, Пример 2 и Пример 3) сетка гораздо больше — квадрат до $16\times16$, взятый из прикреплённого файла. Ручной перебор здесь исключён из-за миллионов маршрутов, но алгоритм абсолютно тот же: две вспомогательные таблицы, формулы максимума и минимума, протянутые на весь диапазон. Применяя описанные шаги к соответствующим файлам, для Примера 1 получаем итоговый ответ 1204502, для Примера 2 — 1212392, для Примера 3 — 1496782. В каждом случае числа получены одинаковым способом: заполнением таблиц $M_{max}$ и $M_{min}$ по всей сетке и считыванием значений из правого нижнего угла — просто масштаб сетки не позволяет привести здесь пошаговое заполнение всех 256 ячеек, поэтому расчёт выполняется в табличном процессоре или программе, а не на бумаге.

Типичные ошибки и ловушки

• Перепутан порядок чисел в ответе. Нужно писать сначала максимум, затем минимум — обратный порядок засчитывается как неверный ответ, даже если оба числа правильные.
• Неверные абсолютные и относительные ссылки в формуле. При протягивании формулы вправо и вниз легко «съехать» ссылкой на соседнюю клетку не в ту сторону — стоит сразу проверить формулу в нескольких соседних ячейках вручную.
• Ошибка в границах таблицы. Первую строку и первый столбец нельзя заполнять общей формулой с $\max$/$\min$ от двух соседей — там путь единственный, и формула должна быть просто накопительной суммой.
• Путаница между максимумом и минимумом монет и суммой пути. Задание просит сумму по всему маршруту, а не самое дорогое или самое дешёвое отдельное значение клетки.
• Неверное определение размера $N$. Если размер таблицы в файле определён неверно (например, включена лишняя строка заголовка), все дальнейшие вычисления окажутся смещены.
• Округление или потеря числа при копировании ответа. Итоговое число нужно переносить в бланк ответа целиком, без пробелов между максимумом и минимумом.

Как готовиться

• Сначала отработать рекуррентные формулы на маленьких сетках ($3\times3$–$4\times4$) с ручной проверкой полным перебором маршрутов — это закрепляет понимание принципа динамического программирования.
• Потренироваться строить в табличном процессоре сразу две вспомогательные таблицы (для максимума и минимума) на одном листе, чтобы формулы протягивания не пересекались.
• Освоить быстрое определение размера таблицы в открытом файле — не пересчитывать строки вручную, а использовать выделение диапазона.
• Прорешать несколько вариантов из открытого банка заданий, каждый раз проверяя порядок чисел в ответе (максимум первым).
• При наличии навыков программирования продублировать решение скриптом — это даёт быстрый способ проверить результат, полученный в таблице, и снижает риск случайной ошибки в формуле.
• Обязательно засекать время выполнения задания на тренировках: цель — уверенно построить обе таблицы и получить ответ за 3–5 минут, не тратя лишнее время на пересчёт вручную.