Квадрат разлинован на 
клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю клетку. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100, либо ничего не лежит (0). Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Робот может перемещаться только на клетки, на которых есть монета.
Определите максимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю клетку, а также количество способов, которыми он может пройти.
В ответе укажите два числа через пробел — сначала максимальную сумму, затем количество способов. Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата.
Нам дано поле 24 на 24, создадим рядом еще одно поле такого же размера (ячейки 
) . В левую верхнюю клетку нового поля, записываем значение из левой верхней клетки исходного поля – 22.
Сначала заполним значениями верхнюю строку. Для этого к значению из левой верхней клетки нового поля, прибавим значение из клетки 
, если она сама или предыдущие не равны 0, сделаем это с помощью формулы:
=ЕСЛИ(ИЛИ(A26=0;B1=0);0;A26+B1)
Теперь, чтобы заполнить оставшиеся ячейки верхней строки нового поля, растянем эту формулу на всю строку. Подобным образом заполним левый столбец нового поля.
Найдем максимальное значение суммы. Рассмотрим ячейку 
, если она не равна 0, в нее мы можем попасть из 
и 
, если они не равны 0, тогда, чтобы в этой клетке суммы была максимальной, необходимо выбрать максимальную сумму из тех двух клеточек, если же одна из клеток 
и 
равна нулю, то нам нужно выбрать второе (а то есть максимальное), а если сама 
равна нулю, то в нее мы попасть не можем и значение в ней будет 0. В ячейку 
запишем формулу:
=ЕСЛИ(B2=0;0;ЕСЛИ(ИЛИ(A27=0;B26=0);МАКС(A27;B26);МАКС(A27;B26)))+B2
Теперь растянем эту формулу на все свободные ячейки поля. В правом нижнем углу будет число, которое является максимальной суммой, которую может собрать робот.
Для подсчета количества путей из левой верхней ячейки в правую нижнюю создадим пустую таблицу такого же размера. В левую верхнюю ячейку запишем 1, так как в эту ячейку можно попасть только одним способом. Ячейчки верхней строки и левого столбца приравниваются к соседней ячейке. В остальных ячейках нужно записать сумму двух соседних ячеек (левой и верхней). Остается только расставить нули в ячеки, в которых в изначальной таблице были нули. Тогда ответ 4671943236924.