Определите минимальную и максимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа - сначала минимальную сумму, затем максимальную.
Примечание.
Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
(В. Лашин) Квадрат разлинован на N × N клеток (1 < N < 30).
Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз.
По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю.
Квадрат ограничен внешними стенами.
Между соседними клетками квадрата также могут быть внутренние стены.
Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100.
Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля - тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой.
Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля.
При разных запусках итоговые накопленные суммы могут различаться.
Определите минимальную и максимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа - сначала минимальную сумму, затем максимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата.
Внутренние и внешние стены обозначены утолщёнными линиями.
Решение 1
Сначала найдём максимальную денежную сумму. Для этого вычислим максимальную сумму для каждой достижимой ячейки поля. Скопируйте границы и стенки на интервал A22:T41.
В ячейку A22 введите формулу =A1.
Для ячеек правее A1 (робот может прийти только слева) в B22 запишите =A22+B1 и скопируйте формулу на первую строку рабочей области до столбца T.
Для ячеек ниже A1 (робот может прийти только сверху) в A23 запишите =A22+A2 и скопируйте формулу вниз по первому столбцу.
В B23 введите =B2+МАКС(B22;A23) и скопируйте на весь диапазон A22:T41.
Для ячеек, у которых справа стена, сумма считается только сверху; если снизу стена — только слева. В недостижимые ячейки запишите 0.
Робот может остановиться в «угловых» клетках; для этого варианта проверьте значения в ячейках: D25, R26, R37, F38, L39, T41.
Получим таблицу:
Максимальная денежная сумма: 316.
Для минимальной суммы замените МАКС на МИН («Найти и заменить»). В недостижимые ячейки поставьте большое число, например 10000.
Получим таблицу:
Минимальная денежная сумма: 2223.
Ответ: 316 и 2223 (в бланк — подряд: 3162223).
Решение 2
Разделим ячейки на следующие типы:
ячейки, в которые можно попасть только слева (зелёные);
ячейки, в которые можно попасть только сверху (красные);
ячейки, в которые невозможно попасть (серые);
конечные ячейки (жёлтые).
В незакрашенные ячейки можно попасть и сверху, и слева.
Скопируем нашу разметку в ячейки под исходной таблицей и удалим оттуда содержимое. Для этого выделяем таблицу и копируем её (Ctrl-C), вставляем её ниже (Ctrl-V) и удаляем содержимое ячеек (Backspace). При этом разметка сохраняется.
В стартовую ячейку A24 впишем формулу =A1.
В ячейку B24 впишем формулу =A24+B1 и скопируем её во все зелёные ячейки.
(Чтобы разметка сохранялась при копировании, можно выполнять вставку через меню: Правка/Вставить как/Вставить только формулы — при этом не изменяется разметка ячеек, в которые производится вставка.)
В ячейку A25 впишем формулу =A24+A2 и скопируем её во все красные ячейки.
В серые ячейки не вписываем ничего: робот не может туда попасть.
В ячейку B25 вписываем формулу =МАКС(A25;B24)+B2 и копируем её в белые и жёлтые ячейки.
В ячейку C45 (или в любую другую свободную) вписываем формулу =МАКС(D27; R28; R39; F40; L41; T43) — максимум по всем жёлтым клеткам.
В этой ячейке появляется результат 316 — максимальная возможная сумма.
Чтобы найти минимальную сумму, выделяем нашу таблицу и ячейку для результата, меняем «МАКС» на «МИН» и получаем ответ 2223.
Твой ИИ-помощник
Подсказки по заданию №18, без готовых формул.
Enter — отправить, Shift+Enter — новая строка.
