Условие: № 10101 Демоверсия 2024 (Уровень: Базовый)
• Статья подготовлена командой itpy, подписывайтесь на наш телеграм канал!
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля - тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа - сначала максимальную сумму, затем минимальную. Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Для выполнения этого задания требуется открыть файл. Ссылка на файл, который необходимо открыть.
Таблица выглядит следующим образом:
Итак, первым делом нужно создать новую таблицу, которая будет являться копией первой, но без заполненных в неё чисел.
Далее ещё раз читаем условие задачи:
Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
Из условия понимаем, что нужно следовать из левой верхней клетки в правую нижнюю. Значит переносим значение из первой таблицы в новую.
Для этого пишем в ячейке A22 = A1
Далее заполняем ячейки справа и снизу от A22. В ячейке B22 пишем =B1+A22, т.е. значение из первой таблицы + предыдущее из новой.
А в ячейке A23 соответственно пишем =A2+A22, т.е. тоже значение из первой таблицы + предыдущее из новой.
Далее растягиваем столбик A и строку B до конца таблицы.
Т.к. робот собирает максимальное число из двух ячеек.
То в ячейку B23 пишем =B2 + МАКС(A23;B22), т.е. робот будет к значению из первой таблицы прибавлять максимальное из верхней или нижней ячейки новой таблицы.
Так как в таблице есть стенки, то для того, чтобы не запутаться, можем выделить их цветом:
Также выделим угловые ячейки, так как есть условие:
В «угловых» клетках поля - тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой.
Далее заполняем все ячейки таблицы, кроме выделенных, функцией из ячейки B23. Пока что их просто запомним.
Должно получиться что-то вроде такого:
Так как в выделенных вертикальных ячейках Робот может идти только вниз, то вставляем в них функцию из ячейки A23. А так как в горизонтальных ячейках Робот может идти только вправо, то вставляем в них функцию из ячейки B22.
В итоге получается такая таблица:
Нам нужно выбрать максимальную сумму из всех угловых ячеек. Вот эти ячейки:
Мы видим, что максимальной суммой будет 2167.
Далее, для того, чтобы найти минимальную сумму, нам необходимо воспользоваться заменой
После замены получится следующая таблица:
Минимальной суммой из этих ячеек будет число 718.