Задача
Квадрат разлинован на
N × N клеток (1 < N < 30). Исполнитель ЭМУ может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд:
вправо или
вверх. По команде
вправо ЭМУ перемещается в соседнюю правую клетку, по команде
вверх – в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стены ЭМУ пройти не может.
В начальный момент времени у ЭМУ имеется запас фруктов, равный числу, записанному в стартовой клетке. При переходе с клетки на клетку ЭМУ съедает определеное число фруктов. При перемещении вправо ЭМУ съедает столько фруктов сколько записанно в клетке, в котороую он перемещается, плюс еще 2. При перемещении вверх ЭМУ съедает удвоенное число фруктов, записанное в клетке, в которую он перемещается, Определите максимальное и минимальное число фруктов, которые останутся в запасе у ЭМУ, пройдя из левой нижней клетки (стартовая клетка) в правую верхнюю.
В ответе укажите два числа – сначала максимальное число, затем минимальное. Оба числа указываются в одной строке через один пробел.
Исходные данные представляют собой электронную таблицу размером
N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщенными линиями.