Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вверх, по диагонали вправо-вверх или по диагонали влево-вверх. Числа показывают расход энергии робота на прохождение клетки.
Определите максимальный и минимальный расход энергии при переходе робота в правую верхнюю клетку поля. В ответе запишите два числа: сначала минимальный расход энергии, затем — максимальный.
Исходные данные записаны в электронной таблице. Пример входных данных (для таблицы размером 4 × 4):
| 42 | 90 | 2 | 44 |
| 72 | 30 | 36 | 63 |
| 62 | 6 | 61 | 42 |
| 21 | 84 | 49 | 50 |
При указанных входных данных минимальный расход получится при движении по маршруту:
а максимальный — при движении по маршруту:
В ответе в данном случае надо записать
Ответ:
В ячейку W21 запишем формулу =B21. Это энергия необходимая роботу для попадания в первую ячейку.
Поскольку робот может двигаться вправо,
Поскольку робот может двигаться вверх или по диагонали влево-вверх,
Теперь посчитаем максимальное количество энергии, необходимой роботу чтобы попасть в ячейку X20.
Поскольку робот умеет ходить на одну клетку вправо, вверх, по диагонали вправо-вверх или по диагонали влево-вверх, то в ячейку X20 можно попасть из ячеек: W20, X21, W21 (через
Составим формулу считающую максимальную энергию для перехода
=МАКС(W21+C20;Y21+C20;X21+C20;W20+C20)
Cкопируем формулу во все ячейки диапазона X20:AP2.
Таким образом,
Теперь найдём минимально возможный расход энергии. Для этого средствами автозамены электронной таблицы (сочетание клавиш CTRL + F) меняем значение МАКС на МИН. Заметим, что в столбце AP из формулы надо убрать возможную дорогу влево-вверх. Для этого
=МИН(AO20+U20;AP21+U20;AO21+U20).
И скопируем формулу
Таким образом,
Ответ: 667 и 4009.