Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля - тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа - сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Сначала целиком копируем наше пространство со всеми стенами без значений.
Изначально робот находится в левом верхнем углу пространства. Возьмем первое значение из ячейки A1. В ячейку A23 вставим формулу: =A1
Если робот будет двигаться вдоль верхней стены, то его сумма монет будет зависеть от предыдущей ячейки в таблице.
В ячейку В23 запишем формулу: = B1+A23
Растягиваем формулу вдоль верхней горизонтальной стены.
Аналогично проделываем с вертикальной стеной.
В ячейках B24:T42 робот уже будет думать брать ему максимальное значение или минимальное. Это можно реализовать с помощью формул МИН и МАКС. Сначала будем искать максимальное значение.
Вставляем следующую формулу в ячейку B24: =B2+МАКС(B23;A24)
Растягиваем нашу формулу на все оставшиеся ячейки в пространстве.
Мы потеряли все наши стенки!!!(((
Ничего страшного, просто скопируем наше пространство заново (обязательно при вставке нажимаем ФОРМАТИРОВАНИЕ).
Теперь работаем со стенками. У нас будет следующая закономерность.
Робот не может пройти сквозь вертикальную стену, когда он двигается вправо.
Робот не может пройти сквозь горизонтальную стену, когда он двигается вниз.
Отметим наши ячейки, в которых нам нужно будет изменить формулы.
В случае с ячейками, которые закрашены синим цветом, нам нужно, чтобы ячейка зависела только от верхней предшествующей ячейки.
Аккуратно меняем значения во всех остальных синих ячейках.
Там, где мы изменили формулу, Excel подсвечивает зелеными флажочками. Это очень удобно.
Аналогично проделаем с оранжевыми ячейками. В этих ячейках у нас зависимость от левой предшествующей ячейки.
И вот мы получили итоговое пространство для нахождения максимального количества монеток. Робот очень старался собрать НАИБОЛЬШЕЕ количество монеток и по итогу решил встать на зарядку в ПРАВОМ НИЖНЕМ УГОЛОЧКЕ. Таких уголков здесь несколько, поэтому нам нужно будет ещё и выбрать с наибольшим числовым значением. Отметим эти уголочки желтым цветом.
Наибольшее значение в самом правом нижнем уголочке. МАКС: 2671
Найдём теперь самое маленькое количество монеток.
Нажимаем ctrl + F (поиск) и выбираем "Заменить".
В "Найти": МАКС
В "Заменить на": МИН
Нажимаем "заменить все".
Значения в нашем пространстве изменились.
Выбираем самое маленькое значение.
МИН 419
ОТВЕТ: 2671 419
Какие сложности могут встречать в этом задании:
1. Могут изменить ходы робота
2. Могут сказать, что робот не собирает монетки, а например тратит их или, что робот забирает эту монетку, если значение четное или нечетное.
Главное внимательно читать условия задачки!