фильтры
выбери формат
задания из КИМ
№18 в КИМ
Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вверх или вправо. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. На поле имеются зеленые клетки, в которые Робот может зайти, сохранив все накопленные ранее монеты, если перед этим количество собранных монет было чётным, в противном случае, он теряет все собранные монеты и начинает сбор с 0 (монеты, находящиеся в клетке, не идут в счет). Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. Определите минимальную и максимальную денежные суммы, которые может собрать Робот, пройдя из левой нижней клетки в верхнюю правую.
Исходные данные записаны в файле в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. Внешние и внутренние стены обозначены утолщёнными линиями. В ответе укажите два числа – сначала минимальную сумму, затем максимальную.
