Задание 18: Робот-сборщик монет

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

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

• ответ — два числа, записанные подряд без пробелов и разделителей;
• порядок фиксирован: сначала максимальная сумма, затем минимальная; …

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