Задание 18
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Пример входных данных
Теория
Задание на умение пользоваться табличным процессором. Удобней MS Excel. Необходимо знание некоторых функций (макс и мин), а также понятие об абсолютной, смешанной и относительной ссылок на ячейки и умение быстро копировать и заполнять большое количество ячеек.
Решение
Итоговая клетка - это клетка которая и снизу и справа ограничена стеной т.е. робот дальше не может ходить. Задайте для удобства этим ячейкам на листе заливку (на рисунке светло-зеленый цвет) и также задайте заливку тем ячейкам в которые робот может попасть только сверху (светло-желтая) и только справа (морской волны). Потом выделите заголовки столбцов и вызовите на выделенных заголовках контекстное меню - Ширина столбца и задайте ширину 4 символа (также для удобства).
Далее выделяем всю нашу таблицу и копируем ее в ячейку A22 - удобно оставить пустую строку и сразу же клавишей Delete удаляем числа - форматы остаются!
Скопированная таблица для поиска максимума (простой заменой также для поиска минимума). Переходим в ячейку A22 и вставляем в нее формулу =A1. В ячейку A23 вставляем формулу =A22+A2 и копируем ее вниз до A41 - выбираем вариант только формулы! Последнее число получилось 1044, для проверки выделите диапазон A1:A20 и в строке состояния (в области автоитогов должна быть та же сумма). Аналогично в B22 вставляем формулу =A22+B1, копируем вправо до ячейки T22 - результат 1018 - проверьте самостоятельно.
Переходим в ячейку B23 и вводим формулу =МАКС(A23; B22)+B2 - минимальное из A23 и B22 + содержимое B2. Результат 136. Копируем эту формулу вниз до B41 - только значения и все формулы с B23 до B41 копируем вправо до ячейки T41 - только значения.
Осталось исправить формулы в светло-желтых и в голубых ячейках. В каждой группе светло-желтых ячеек в верхнюю ячейку можно попасть только сверху! В ячейке E26 вводим формулу =E25+E5 и копируем ее вниз на 9 ячейки (до последней желтой в группе - только значения). Повторяем в остальных группах. Аналогично с голубыми ячейками. В ячейке B26 вводим формулу =A26+B5 и копируем вправо до D26 (до последней голубой в группе - только значения). Повторяем со всеми оставшимися голубыми. Признаком того, что в цветных ячейках вы исправили формулы - значок зеленой галочки в левом верхнем углу ячейки (предупреждение - формула не согласуется с соседними).
Просмотрите и сравните содержимое светло-зеленых ячеек или в ячейке U41 введите формулу =МАКС(L41;R36;T41) - результат 2167.
Для нахождения минимума выполните команду Правка - заменить и заменить МАКС на МИН
Ответ
2167 и 718 (Время не более 10 минут)