Задача #2815

(М. Попков) На ежегодных соревнованиях роботов в ТехноГраде участникам предстояло управлять роботом по квадрату размером N x N, каждая клетка которого содержала монеты с денежной суммой от 1 до 100. Маршруты роботов начинались из любой стартовой клетки, которая справа и снизу ограничена стенами, включая правую нижнюю клетку поля, и заканчивались в одной из угловых клеток, ограниченных стенами слева и сверху, включая левую верхнюю клетку поля.

Робот мог выполнять только следующие команды:

1) Влево – перемещение в соседнюю клетку, которая находится слева.

2) Вверх – перемещение в соседнюю клетку, которая находится сверху.

3) Диагональ – перемещение одновременно влево и вверх.

Квадрат был окружён внешними стенами, а между клетками могли быть внутренние стены, через которые робот пройти не мог. Каждая клетка, в которую попадал робот, добавляла денежную сумму монеты к его общему счёту. Это касалось начальной и конечной клеток маршрута.

Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из «начальной» клетки маршрута в «конечную». В ответе укажите два числа — сначала максимальную сумму, затем минимальную.