Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз. Выходить за пределы поля робот не может. Между некоторыми клетками находятся стены, проходить сквозь стены робот не может.
В начальный момент запас энергии робота равен числу, записанному в стартовой клетке. При каждом шаге робот расходует энергию. При шаге вниз расход энергии равен числу, записанному в клетке, в которую переходит робот, при шаге вправо — удвоенному числу, записанному в клетке, в которую переходит робот.
Определите максимальный и минимальный запас энергии, который может быть у робота после перехода в правую нижнюю клетку поля. В ответе запишите два числа: сначала максимально возможное значение, затем минимальное.
Исходные данные записаны в электронной таблице. Стены отмечены утолщёнными линиями.
Пример входных данных (для таблицы размером 4 × 4):
| 500 | 8 | 69 | 50 |
| 30 | 35 | 57 | 17 |
| 32 | 1 | 9 | 32 |
| 44 | 12 | 80 | 43 |
При указанных входных данных максимальное значение получается при движении по маршруту
500 − 2 · 8 − 35 − 2 · 57 − 2 · 17 − 32 − 43 = 226,
а минимальное при движении по маршруту
500 − 30 − 32 − 44 − 2 · 12 − 2 · 80 − 2 · 43 = 124.
Ответ:
Сначала найдём максимально возможный запас энергии.
Для ячеек диапазонов D24:D26, J20:J22 и L26:L28, поскольку слева от них имеются стены, запас энергии будет вычисляться аналогично диапазону A18:A31. В ячейку D24 запишем формулу =D23-D8 и скопируем её во все ячейки диапазонов D25:D26, J20:J22 и L26:L28. Для ячеек диапазонов D27:F27, J23:L23 и L29:N29, поскольку сверху от них имеются стены, запас энергии будет вычисляться аналогично диапазону B17:O17. В ячейку D27 запишем формулу =C27-2*D11 и скопируем её во все ячейки диапазонов E27:F27, J23:L23 и L29:N29.
Для остальных ячеек будем сравнивать значение разности ячейки слева и удвоенного исходного значения текущей ячейки, значение разности ячейки сверху и исходного значения текущей ячейки, максимальное из сравниваемых значений будем записывать в текущую ячейку.
=МАКС(A18-2*B2;B17-B2)
и скопируем её во все ячейки
Минимально возможный запас энергии находится аналогичным образом. Ячейки диапазонов B17:O17 и A18:A31 будут принимать такие же значения, как и при поиске максимально возможного значения. Для ячеек диапазонов D24:D26, J20:J22 и L26:L28, поскольку слева от них имеются стены, запас энергии будет вычисляться аналогично
Для остальных ячеек будем сравнивать значение разности ячейки слева и удвоенного исходного значения текущей ячейки, значение разности ячейки сверху и исходного значения текущей ячейки, минимальное из сравниваемых значений будем записывать в текущую ячейку.
=МИН(A18-2*B2;B17-B2)
и скопируем её во все ячейки
Ответ: 1825 и 236.