18 задание ЕГЭ информатика

Q: Сколько баллов даёт задание 18 ЕГЭ по информатике?

Максимум – 1 первичный балл. Норма времени на экзамене – около 8 мин. Уровень сложности – П.

Q: Как подготовиться к заданию 18?

Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.

Робот: динамическое программирование в таблице

1 балл ≈ 8 мин уровень П Электронные таблицы: динамическое программирование (Робот)

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

Идея ДП: лучшая сумма в клетке = монета в клетке + лучшая из сумм в клетках, откуда можно прийти (сверху и слева), если между ними нет стены.

Алгоритм в Excel

Скопируй поле рядом (например, начиная со столбца W). Стены на копии видны, если копировать вместе с форматом.
В левую верхнюю клетку копии: =A1.
Первая строка: =X1+B1 (только слева), первый столбец: =W1+A2 (только сверху).
Остальные клетки: =МАКС(X1; W2)+B2 – максимум из «сверху» и «слева» плюс монета.
Там, где стена слева – формула только «сверху»: =X1+B2; где стена сверху – только «слева». Исправь такие клетки вручную.
Ответ – значение в конечной клетке. Для минимума повтори с МИН.

То же на Python (поле без внутренних стен):

g = [list(map(int, line.split())) for line in open("18.txt")]
n = len(g)
dp = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        prev = []
        if i > 0: prev.append(dp[i - 1][j])
        if j > 0: prev.append(dp[i][j - 1])
        dp[i][j] = g[i][j] + (max(prev) if prev else 0)
print(dp[n - 1][n - 1])

Разобранный пример. Поле 3 × 3: 1 2 3 / 4 5 6 / 7 8 9. Максимум: 1 → 4 → 7 → 8 → 9 = 29. Минимум: 1 → 2 → 3 → 6 → 9 = 21.

Ловушки: не исправить формулу у стены – Робот «пройдёт сквозь» неё; конечных клеток может быть несколько («угловые» клетки, ограниченные стеной справа и снизу) – тогда возьми максимум/минимум по всем таким клеткам; не забыть монету стартовой клетки.

На экзамене

Сначала найди все стены и отметь клетки, где формулу нужно менять.
Протяни формулу МАКС на всё поле, затем точечно исправь клетки у стен.
Сделай две копии поля – для максимума и минимума отдельно.

Разобранные задания 18 из открытого банка ФИПИ

Пример 1 · код ФИПИ 79404A

Рисунок к заданию

Задание выполняется с использованием прилагаемых
файлов.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз $-$
в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки
в правую нижнюю. В ответе укажите два числа $-$ сначала максимальную сумму, затем минимальную.

Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

Пример входных данных:

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

Файл к заданию (ZIP)

Показать ответ и решение

Ответ: 2794 1693

Динамическое программирование по клеткам: в клетку приходим слева или сверху, если между клетками нет стены (утолщённой границы); берём максимум/минимум и добавляем монету.

Максимум 2794, минимум 1693.

Пример 2 · код ФИПИ 2285C9

Рисунок к заданию

Задание выполняется с использованием прилагаемых
файлов.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз –
в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки
в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Пример входных данных

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

Файл к заданию (ZIP)

Показать ответ и решение

Ответ: 2285 993

Динамика по таблице: в клетку можно прийти слева или сверху, если между клетками нет стены (толстой границы); храним максимум и минимум суммы.

Финиш – правая нижняя клетка. Максимум 2285, минимум 993.

Пример 3 · код ФИПИ 82DB4B

Рисунок к заданию

Задание выполняется с использованием прилагаемых
файлов.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель
Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз $-$ в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

В «угловых» клетках поля $-$ тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.

Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа $-$ сначала максимальную сумму, затем минимальную.

Пример входных данных

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

Файл к заданию (ODS)

Показать ответ и решение

Ответ: 2320 860

Стены берём из утолщённых границ ячеек файла; конечные клетки – со стенами справа и снизу (их 4). Динамика max/min до каждой клетки.

Максимум 2320, минимум 860.

Частые вопросы о задании 18

Сколько баллов даёт задание 18 ЕГЭ по информатике?

Максимум – 1 первичный балл. Норма времени на экзамене – около 8 мин. Уровень сложности – П.

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

Как подготовиться к заданию 18?

Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.