Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вниз, по диагонали вправо-вниз или по диагонали влево-вниз. Числа показывают расход энергии робота на прохождение клетки.
Определите максимальный и минимальный расход энергии при переходе робота в правую нижнюю клетку поля. В ответе запишите два числа: сначала минимальный расход энергии, затем — максимальный.
Исходные данные записаны в электронной таблице. Пример входных данных (для таблицы размером 4 × 4):
| 42 | 90 | 2 | 44 |
| 72 | 30 | 36 | 63 |
| 62 | 6 | 61 | 42 |
| 21 | 84 | 49 | 50 |
При указанных входных данных минимальный расход получится при движении по маршруту:
а максимальный — при движении по маршруту:
В ответе в данном случае надо записать
Ответ:
В ячейку W2 запишем формулу =B2. Это энергия необходимая роботу для попадания в первую ячейку.
Поскольку робот может двигаться вправо,
Поскольку робот может двигаться вниз или по диагонали влево-вниз,
=МАКС(W2+B3;X2+B3),
столько энергии требуется роботу для перехода на одну ячейку вниз. Скопируем эту формулу
Теперь посчитаем максимальное количество энергии, необходимой роботу чтобы попасть
Поскольку робот умеет ходить на одну клетку вправо, вниз, по диагонали вправо-вниз или по диагонали влево-вниз, то
Составим формулу считающую максимальную энергию для перехода
=МАКС(X2+C3;W3+C3;Y2+C3;W2+C3).
Cкопируем формулу во все ячейки диапазона X3:AP21.
Таким образом,
Теперь найдём минимально возможный расход энергии. Для этого средствами автозамены электронной таблицы (сочетание клавиш CTRL + F) меняем значение МАКС на МИН. Заметим, что в столбце AP из формулы надо убрать возможную дорогу влево-вниз. Для этого
=МИН(AP2+U3; AO3+U3;AO2+U3).
И скопируем формулу в диапазон AP3:AP21.
Таким образом,
Ответ: 742 и 4054.