Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое число. В некоторых клетках записано
За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх. Клетка, из которой робот не может сделать допустимого хода (справа и сверху находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток.
В начальный момент робот обладает некоторым запасом энергии. Расход энергии на запуск робота равен числу, записанному в стартовой клетке.
В дальнейшем расход энергии на шаг из одной клетки в другую равен максимальному из двух чисел, записанных в этих клетках.
Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до какой-нибудь финальной клетки.
Задание 2. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.
Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на
Ответ:
Для поиска минимального значения будем работать с областью B23:U42, так как при расчетах будем использовать исходные значения энергии в каждой клетке.
В ячейку B42 напишем значении =B21.
Для каждой ячейки левого столбца это будет сумма энергии нижней ячейки и максимального значения из двух ячеек: текущей и нижней. Внесем
Для каждой ячейки строки это будет сумма энергии предыдущей ячейки и максимального значения из двух ячеек: текущей и левой. Внесем
Далее в ячейку C41 вставим формулу =МИН(B41+МАКС(B20:C20);C42+МАКС(C20:C21)) и скопируем за маркер
В ячейки отмеченные серым цветом робот заходить не может, в них поставим заведомо большее число, чтобы при выборе минимального значения в ячейке робот не учитывал эти ячейки.
В результате получим следующую таблицу:
Финальными клетками для робота могут быть ячейки: D29, L32, H39, R37, U23.
Определите минимальный начальный запас энергии, который позволит роботу добраться до какой-нибудь финальной клетки. Для этого введем формулу:=МИН(D29;H39;L32;R37;U23)). Значение минимального начального запаса энергии, который позволит роботу добраться до какой-нибудь финальной клетки, — 549.
Определим минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки. Для этого введем формулу:=МАКС(D29;H39;L32;R37;U23). Значение минимального начального запаса энергии, который позволит роботу добраться до любой финальной клетки, — 1605.
Ответ: 549&1605.

