КЕГЭ 18 Динамический подсчет с Роботом

​Задание 18 по информатике связано с динамическим подсчетом в таблицах. Это распространенный подход к решению задач на ЕГЭ, где большая и сложная задача разбивается на серию более простых подзадач. Решение каждой последующей подзадачи опирается на результаты предыдущих, что позволяет постепенно прийти к ответу на общую задачу.

Посмотрим пример с которым мы уже знакомились раньше

​Робот перемещается по полю, собирая монеты или затрачивая энергию.

• Начальная точка: Робот обычно начинает с угловой клетки и идет в противоположный угол.

• Правила перемещения: Чаще всего робот может двигаться только в двух направлениях в сторону финиша.

• Цель: Определить максимальную или минимальную сумму, которую робот может собрать, дойдя из начальной клетки в конечную.

Пример 1

• Для первой клетки сумма равна значению самой клетки.

• Для клеток в первой строке (если движение только вправо), сумма равна предыдущей накопленной сумме плюс значение текущей клетки.

• Аналогично для клеток в первом столбце (если движение только вниз), сумма равна предыдущей накопленной сумме плюс значение текущей клетки.

• Для внутренних клеток, куда можно попасть несколькими способами, выбирается максимальная или минимальная сумма из всех возможных путей до этой клетки, затем к ней прибавляется значение текущей клетки.

  • Пример формулы для максимальной суммы: =МАКС(сумма_слева + текущая_ячейка; сумма_сверху + текущая_ячейка).

Внутренние стены

• Робот не может пересекать стены.

  • Если стена находится справа, движение вправо невозможно, и формула для этой клетки должна учитывать только движение сверху.

  • Если стена находится снизу, движение вниз невозможно, и формула должна учитывать только движение слева.

  • Для учета стен необходимо скопировать соответствующую формулу (например, из первой строки или столбца) в ячейки, где стена ограничивает движение.

​Пример 2

Тупики

• Тупиковые клетки: В некоторых вариантах заданий определенные клетки являются конечными, если справа или снизу от них стоит стена.

  • В этом случае необходимо найти максимальную/минимальную сумму среди всех возможных тупиковых клеток, а не только в финишной клетке.

Недоступные зоны

• Недоступные зоны: Некоторые области поля могут быть недоступны для робота из-за правил перемещения (например, только вправо и вниз, но стена закрывает путь). Такие зоны следует рассматривать как стены.

Специальные условия

• Выборочный сбор монет (четные/нечетные): Робот может собирать монеты только из клеток с четным количеством монет.

  • Решение: Создать копию таблицы, где нечетные числа заменены на 0, а четные остаются без изменений. Затем производить расчеты на этой модифицированной таблице.

Специальные условия

• Запретные клетки (стены по значению): Робот разрушается, если заходит в клетки, содержащие числа в определенном диапазоне (например, от 100 до 500).

  • Решение для максимальной суммы: Заменить значения в запретных клетках на очень маленькое отрицательное число (например, -10000). Это сделает путь через них крайне невыгодным, и динамический подсчет будет их "обходить".

  • Решение для минимальной суммы: После замены МАКС на МИН, также необходимо заменить -10000 на очень большое положительное число (например, 10000), чтобы сделать эти пути невыгодными для минимума.

Различные команды движения и удвоение вознаграждения

• Робот может иметь больше двух команд (например, вправо, вниз, по диагонали (вправо-вниз)). При этом, при движении по диагонали вознаграждение может удваиваться.

  • Решение: В формуле МАКС/МИН для каждой клетки учитывать все возможные пути (например, три варианта) и соответствующее изменение вознаграждения (например, +2*ячейка для диагонального хода)