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

Задача . Задача 5


Задача

Темы:
Робот  стоит  в  левом  нижнем  углу  прямоугольного  поля,  в  каждой  клетке которого  записано  целое  положительное  число.  За  один  ход  робот  может переместиться на одну клетку вправо или на одну клетку вверх. Некоторые клетки выделены тёмным фоном. В эти клетки роботу заходить нельзя. Клетка,  из  которой  робот  не  может  сделать  допустимого  хода  (справа и сверху  находятся  границы  поля  или  запрещённые  клетки),  называется финальной. На поле может быть несколько финальных клеток. В  начальный  момент  робот  обладает  запасом  энергии,  которая  расходуется на  движение  по  клеткам.  Расход  энергии  на  прохождение  каждой клетки, включая стартовую и финальную, равен числу, записанному в этой клетке.
Задание  1.  Определите  минимальный  начальный  запас  энергии,  который позволит роботу добраться до какой-нибудь финальной клетки.
Задание  2. Определите  минимальный  начальный  запас  энергии,  который позволит роботу добраться до любой финальной клетки.
В  обоих  заданиях  энергии  должно  хватить  и  на  прохождение  финальной клетки.
Исходные  данные  записаны  в  электронной  таблице.  В  ответе  запишите  два числа: сначала ответ на задание 1, затем ответ на задание 2.
Файл

 

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

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