Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое число. В некоторых клетках записано
За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз. Клетка, из которой робот не может сделать допустимого хода (справа и снизу находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток.
В начальный момент робот обладает некоторым запасом энергии. Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на переход в каждую следующую клетку равен числу, записанному в этой клетке.
Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.
Задание 2. Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом.
Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на задание 1, затем ответ на задание 2.
Для поиска минимального значения будем работать с областью B23:U42, так как при расчетах будем использовать исходные значения энергии в каждой клетке.
В ячейку B23 напишем значении =B21.
Для каждой ячейки левого столбца это будет сумма энергии нижней ячейки и текущей ячейки: текущей и нижней. Внесем
Для каждой ячейки строки это будет сумма энергии предыдущей ячейки и текущей ячейки. Внесем
Далее в ячейку C24 вставим формулу =C3+МАКС(C23;B24) и скопируем за маркер
В ячейки отмеченные серым цветом робот заходить не может, в них поставим заведомо большее число, чтобы при выборе минимального значения в ячейке робот не учитывал эти ячейки.
В результате получим следующую таблицу:
Финальными клетками для робота могут быть ячейки: E29, O28, N38, U42.
Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки. Для этого введем формулу:=МАКС(E29;N38;O28;U42). Значение минимального начального запаса энергии, который позволит роботу добраться до любой финальной клетки, — 1253.
Определим минимальный начальный запас энергии, который позволит роботу который позволит роботу пройти любым допустимым маршрутом. Для этого произведем замену всех формул с МИН на МАКС. В ячейки отмеченные серым цветом робот заходить не может, в них поставим заведомо меньшее число, чтобы при выборе минимального значения в ячейке робот не учитывал эти ячейки. Получим таблицу:
Значение минимального начального запаса энергии, который позволит роботу пройти любым допустимым маршрутом, — 2494.
Ответ: 1253&2494.

