Задача

Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

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

Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.

Пример входных данных:

Для указанных входных данных ответом должна быть пара чисел

Решение

Откроем файл с исходными данными. В нем квадрат 10х 10 заполнен натуральными значениями от 1 до 100. Эти данные являются исходными, их изменять нельзя.

Все вычисления будем делать ниже, на свободном месте. Создадим таблицу размером 10x10, которая будет заполнена значениями, которые покажут сумму, которую собрал Робот, когда он пришел в эту ячейку и подобрал лежащие там монетки.

Начнем заполнение таблицы с ячейки А12. Это стартовая позиция Робота. Все, что есть у него на данный момент - монетка, лежащая в левом верхнем углу. Запишем формулу =А1.

Далее будем заполнять первый (левый) столбец нижней таблицы. Робот может пройти его только сверху вниз, поэтому в каждую следующую клетку он приносит то, что уже собрал (в клетке выше) плюс забирает то, что находится в этой клетке. Для ячейки А13 запишем формулу, которая вычисляет это значение: =А12+А2 (А12 - то, что он собрал ранее из клетки сверху и А2 - то, что забирает в этой клетке). Скопируем формулу из ячейки А13 в диапазон А13:А21.

Аналогично заполним верхнюю строку. Робот может прийти только слева, сверху ячеек нет, поэтому формула в ячейке В12 примет вид =А12+В1. Скопируем формулу из ячейки B12 в диапазон С12:J12.

Теперь необходимо заполнить оставшуюся часть таблицы. Начнем заполнение с ячейки В13. Робот может попасть в эту клетку либо из клетки А13, слева, либо из клетки В12, сверху. Мы вычисляем путь с максимальной эффективностью. Поэтому нам надо определить, откуда в эту клетку выгоднее перейти Роботу, сумму была максимальной. Для этого необходимо выбрать максимальное из двух значений. В В13 формула примет вид =МАКС(А13;В12)+В2.

Далее копируем формулу сначала в диапазон В14:В21, а затем, формулы диапазон В13:В21, копируем в диапазон С13:J21.

В ячейке J21 появилось значение максимальной суммы, которую Робот может собрать по пути: 1204 монеты.

Аналогично вычислим значение минимальной суммы. Последовательность шагов будет та же, только в ячейке В13 надо записать формулу выбора не максимального, а минимального значения =МИН(А13;В12)+В2 и скопировать эту формулу на весь диапазон. В ячейке J21 получим искомое значение 502.

Ответ: 1204 502.