Исполнитель Робот может перемещаться по клеткам, выполняя за одно
Условие
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами.
Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
Задание 18 Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа — сначала максимальную сумму, затем минимальную.
| Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями Пример входных данных:1 | 8 | 8 | 4 |
|---|---|---|---|
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Ответ:
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Сначала найдём максимальную денежную сумму. Для этого найдём максимальную денежную сумму для каждой ячейки таблицы. В ячейку A22 запишем формулу =A1. В ячейку A23 запишем формулу =А22+A1. Скопируем эту формулу во все ячейки в диапазоне А22:А41. В ячейку B22 запишем формулу =А22+B1. Скопируем эту формулу во все ячейки в диапазоне B22:T22.В ячейку B23 запишем формулу =B2+МАКС(B22;A23). Скопируем эту формулу во все ячейки в диапазоне B23:T41. Для ячеек E28:E35, I31:I38, M31:M38, R28:R35, T23:T3, поскольку слева от них имеется внутренняя стенка, максимальная денежная сумма вычисляется как сумма текущей ячейки и суммы сверху. В ячейку E28 запишем формулу =E27+E7 и скопируем эту формулу во все ячейки в диапазоне E28:E35. В ячейку I31 запишем формулу =I30+I10 и скопируем эту формулу во все ячейки в диапазоне I31:I38. В ячейку M31 запишем формулу =M30+M10 и скопируем эту формулу во все ячейки в диапазоне M31:M38. В ячейку R28 запишем формулу =R27+R7 и скопируем эту формулу во все ячейки в диапазоне R28:R35. В ячейку T23 запишем формулу =T22+T2 и скопируем эту формулу во все ячейки в диапазоне T23:T30. Для ячеек B23:F23, F25:J25, J27:N27, поскольку сверху от них имеется внутренняя стенка, максимальная денежная сумма вычисляется как сумма текущей ячейки и суммы слева. В ячейку B24 запишем формулу =A24+B3 и скопируем эту формулу во все ячейки в диапазоне B24:F24. В ячейку F26 запишем формулу =E26+F5 и скопируем эту формулу во все ячейки в диапазоне F26:J26. В ячейку J28 запишем формулу =I28+J7 и скопируем эту формулу во все ячейки в диапазоне J28:N28.Таким образом, в ячейке T41 получим значение максимальной денежной суммы —
Осталось ещё 1 шаг
Аналогичным образом найдём значение…
Бесплатно · займёт минуту