Задание повышенного уровня, проверяющее умение использовать электронные таблицы для обработки целочисленных данных. На его выполнение отводится около восьми минут.
Условие задачи
Квадратная сетка размером N×N клеток. Робот перемещается по клеткам, выполняя команды «вправо» или «вниз». Команда «вправо» перемещает робота в соседнюю правую клетку, команда «вниз» – в соседнюю нижнюю. Квадрат ограничен внешними стенами, между соседними клетками могут быть внутренние стены, которые робот пройти не может. В каждой клетке находится монета достоинством от 1 до 100. Посетив клетку, робот забирает монету (включая начальную и конечную клетки). Необходимо определить максимальную и минимальную суммы, которые может собрать робот, пройдя из левой верхней клетки в правую нижнюю. В ответе указать два числа: сначала максимальную сумму, затем минимальную.
(Пример таблицы с монетами и стенами может быть легко воспроизведён на основе описания задачи)
Решение задачи
Задача решается методом динамического программирования.
Робот начинает движение из левой верхней клетки. Попадая в клетку, он забирает монету. Он может двигаться только вправо или вниз.
Решение с помощью электронной таблицы
- Вспомогательная таблица: Создаётся таблица такого же размера, как исходная, содержащая суммы монет. Значения в ячейках изначально пусты, сохраняются только границы.
- Расчёт для верхнего ряда и левого столбца:
- В левой верхней клетке записывается значение монеты из исходной таблицы.
- Для остальных клеток верхнего ряда сумма рассчитывается как сумма в предыдущей (левой) клетке вспомогательной таблицы плюс значение монеты из соответствующей ячейки исходной таблицы.
- Аналогично рассчитывается сумма для левого столбца, используя значение сверху.
- Расчёт максимальной суммы: Для остальных клеток, используя функцию МАКС, выбирается максимальное значение из сумм в ячейках сверху и слева, прибавляется значение монеты из соответствующей ячейки исходной таблицы.
- Учёт внутренних стен: В ячейках, ограниченных стеной слева, используется только путь «вниз» (сумма из ячейки сверху + значение монеты). В ячейках, ограниченных стеной сверху, используется только путь «вправо» (сумма из ячейки слева + значение монеты).
- Расчёт минимальной суммы: Для нахождения минимальной суммы, вместо функции МАКС используется функция МИН в соответствующих ячейках.
Результаты
Максимальная сумма: 1099. Минимальная сумма: 1026.