Разборы · ЕГЭ, задание 18

Задание 18 ЕГЭ по информатике: Робот и динамическое программирование

Что проверяет задание

Поле N × N из электронной таблицы, в каждой клетке монета. Робот ходит только вправо и вниз, стены (толстые линии) проходить нельзя. Нужно найти максимальную и минимальную сумму монет, которую Робот может собрать. 1 балл за оба верных числа.

Что нужно знать

• Динамическое программирование: лучшая сумма для клетки = монета клетки + лучшее из значений соседей, откуда можно прийти (или куда можно уйти).
• В электронной таблице это одна формула, которую протягивают на всё поле, а у стен правят вручную: =A1+МАКС(B1;A2) и т. п.
• Стены — это форматирование ячеек (границы). Формулы их не видят, поэтому учитывать стены приходится вручную.

Как решать в таблице

1. Скопируйте поле на свободное место — рядом создайте поле для максимума.
2. В левой верхней клетке — сама монета. В первой строке — сумма с соседом слева, в первом столбце — с соседом сверху.
3. В остальных клетках: монета + МАКС(слева; сверху). Там, где слева или сверху стена, берите только доступного соседа.
4. Для минимума — то же с МИН.

Пример из демоверсии 2027

В демоверсии конечных клеток может быть несколько: «угловые» клетки, ограниченные стенами справа и снизу, из которых Робот дальше идти не может. Нужны максимальная и минимальная итоговые суммы среди всех маршрутов из левой верхней клетки.

Когда конечных клеток несколько, удобнее считать динамику с конца: для каждой клетки — лучшая сумма, которую можно собрать, начав с неё. Если справа и снизу стены, клетка конечная и её значение — сама монета. Ответ — значение левой верхней клетки. Стены выписываем по виду таблицы (нумерация с 1):

import pandas as pd

a = pd.read_excel("18.ods", header=None).values.tolist()   # для .ods нужен odfpy
n = len(a)

# Вертикальные стены: справа от клеток столбца col в строках r1..r2
right = {(r - 1, col - 1)
         for col, r1, r2 in [(2, 3, 6), (9, 3, 10), (13, 4, 10), (11, 8, 14),
                             (19, 8, 14), (3, 14, 17), (17, 17, 20)]
         for r in range(r1, r2 + 1)}
# Горизонтальные стены: снизу от клеток строки row в столбцах c1..c2
down = {(row - 1, c - 1)
        for row, c1, c2 in [(2, 6, 9), (3, 14, 17), (6, 3, 7), (14, 8, 11),
                            (14, 17, 19), (16, 13, 17), (17, 4, 8)]
        for c in range(c1, c2 + 1)}

mx = [[0] * n for _ in range(n)]
mn = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
    for j in range(n - 1, -1, -1):
        nxt = []
        if j < n - 1 and (i, j) not in right:
            nxt.append((i, j + 1))
        if i < n - 1 and (i, j) not in down:
            nxt.append((i + 1, j))
        if not nxt:                                  # «угловая» клетка
            mx[i][j] = mn[i][j] = a[i][j]
        else:
            mx[i][j] = a[i][j] + max(mx[p][q] for p, q in nxt)
            mn[i][j] = a[i][j] + min(mn[p][q] for p, q in nxt)
print(mx[0][0], mn[0][0])

Для файла демоверсии (поле 20 × 20): 2598 803.

Типичные ошибки

• Протягивают формулу через стену — Робот «проходит» сквозь неё. Отметьте стены на копии поля заливкой, прежде чем писать формулы.
• Забывают, что монеты начальной и конечной клеток тоже входят в сумму.
• Путают порядок в ответе: сначала максимум, потом минимум.
• Ошибаются на единицу при выписывании стен — сверяйте номера строк и столбцов по заголовкам таблицы.

Потренироваться: задание 18 новые варианты с проверкой ответа