Олимпиадный тренинг

Задача . 39591


Задача

Темы:

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

Перед каждым запуском Робота он обладает запасом энергии в 5000 единиц. В каждой клетке квадрата указано количество энергии, которое Робот потратит, перемещаясь в данную клетку; это также относится к начальной и конечной клеткам маршрута Робота. Некоторые клетки являются труднопроходимыми для Робота. На перемещение в них Робот тратит двойную энергию, указанную в таких клетках. Такие клетки обозначены ячейками с красным фоном.

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

 

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

 

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


 

Если начальный запас энергии Робота равен 100 единиц, то для указанных входных данных ответом должна быть пара чисел: 76 54

Скачать файл


time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя