Задание 18 ЕГЭ по информатике 2027 — робот, стены границами ячеек и несколько угловых клеток
Разбор задания 18 ЕГЭ по информатике 2027: один лист без заголовка, стены — утолщённые границы ячеек, Робот останавливается в любой угловой клетке. Демо: ответ 2598 803, а в правом нижнем углу 2553 и 1162. Calc и Python.
Задание 18 в 2027 году — Робот на квадратном поле, который ходит вправо и вниз и собирает монеты. Форма та же, что в демоверсии 2026: лист один, без заголовка; стены нарисованы утолщёнными границами ячеек; Робот останавливается в любой «угловой» клетке, где справа и снизу стена или край поля. Таких клеток несколько, и ответ — наибольшая и наименьшая итоговые суммы среди всех. В демо их четыре, ответ 2598 803, а в правом нижнем углу — 2553 и 1162: кто смотрит только на угол, ошибается в обоих числах.
Ниже — условие, разбор типового примера 4 × 4 руками, путь через LibreOffice Calc, код на Python, который читает границы из файла и печатает ответ, и ловушки. Динамика по прямоугольнику без стен и с запрещёнными клетками разобрана в статье о задании 18 — идея та же, добавляются стены-границы и несколько конечных клеток.
Условие демоверсии 2027
Квадрат разлинован на 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
Черта | — стена справа от клетки, ---- — стена снизу. Ответ ФИПИ для файла демо: 2598 803.
Разбор типового примера руками
Найдём угловые клетки. У клетки со значением 1 во второй строке (вторая слева) стена справа и стена снизу — угловая. У соседней единицы справа стена есть, а снизу нет — Робот пойдёт вниз. У двенадцати стена справа, снизу свободно — не угловая. Правый нижний угол — угловая всегда. Итого две конечные клетки.
| Угловая клетка | Пути из левого верхнего угла | Суммы |
|---|---|---|
| 1 (вторая строка, второй столбец) | 1 → 8 → 1 и 1 → 10 → 1 | 10 и 12 |
| 6 (правый нижний угол) | все пути вправо-вниз с обходом стен | от 28 до 41 |
Наибольшая сумма в угол: 1 → 8 → 8 → 1 → 12 → 5 → 6 = 41 (через третий столбец вниз, обходя стену справа от двенадцати). Наименьшая в угол: 1 → 10 → 1 → 2 → 3 → 5 → 6 = 28, по первому столбцу вниз. Но наименьшая итоговая сумма — 10, в кармане второй строки. Ответ для примера: 41 и 10. Минимум не в углу — это и есть ловушка номера.
Демо-файл: 20 × 20 и четыре угловые клетки
| Угловая клетка (строка, столбец) | Наибольшая сумма | Наименьшая сумма |
|---|---|---|
| 14, 11 | 1774 | 803 |
| 14, 19 | 1620 | 1003 |
| 20, 17 | 2598 | 1346 |
| 20, 20 (правый нижний угол) | 2553 | 1162 |
Максимум — в угловой клетке нижней строки: стена справа от семнадцатой клетки останавливает Робота с почти полным маршрутом по дорогим монетам. Минимум — в кармане четырнадцатой строки: короткий маршрут через дешёвые клетки. Угол даёт 2553 и 1162, и оба числа неверны.
Решение в LibreOffice Calc
- Скопируй таблицу ниже или правее исходной — это будет таблица наибольших сумм.
- В первой клетке копии поставь ссылку на первую клетку исходной таблицы.
- Формула для остальных клеток: монета плюс максимум из верхнего и левого соседа копии. Для первой строки — только левый сосед, для первого столбца — только верхний.
- Стены. Там, где над клеткой стена, из формулы убирают верхнего соседа; где слева стена — левого. Ячейки со стенами удобно залить цветом в исходной таблице, чтобы не пропустить.
- Клетки без входа. Если у клетки стена и сверху, и слева (в первой строке или первом столбце — со стороны единственного соседа), Робот в неё не попадает. Впиши в неё −1000000 вместо формулы: это число само уйдёт во все клетки, куда можно попасть только через неё, и они тоже станут недостижимыми. Оставить там одну монету нельзя — получится сумма пути, которого нет. В демо такая клетка одна — (4, 14), и за ней недостижимый карман из 28 клеток в строках 4–10 и столбцах 14–17; без этого шага минимум выходит 467 вместо 803.
- Угловые клетки. Пройди по исходной таблице и отметь все клетки со стеной справа и снизу (или краем поля). Ответ на максимум — наибольшее из значений копии в этих клетках; недостижимые, около −1000000, в ответ не идут.
- Минимум. Скопируй таблицу формул ещё раз, замени МАКС на МИН (Ctrl+H по выделенному диапазону), а −1000000 — на 1000000. Наименьшее из значений в угловых клетках — второе число ответа.
Самые уязвимые места — шаги 4 и 5: одна пропущенная стена или клетка без входа меняет значения во всей области ниже и правее. Приёмы работы с формулами и заменой — в справочнике по Calc.
Решение на Python
Этот код — для тренировки дома или в Python-панели кабинета: он читает файл библиотекой odfpy. ФИПИ в инструкции называет только категории программ — текстовый редактор, редактор таблиц и системы программирования, а в опубликованных регионами перечнях ПО — сами среды Python, без сторонних библиотек. Рассчитывать на odfpy на экзамене нельзя. Стандартной библиотекой границы тоже читаются (.ods — zip-архив с XML-файлом content.xml), но такой код длиннее. На экзамене решай в Calc или выпиши стены вручную (обходной путь — ниже).
Стены лежат в стилях ячеек. Библиотека odf (пакет odfpy) читает их: у ячейки свой стиль или стиль колонки по умолчанию, а линия может быть записана у любой из двух соседних ячеек — правая граница левой или левая граница правой. Код учитывает оба случая.
from odf.opendocument import load
from odf.style import Style, TableCellProperties
from odf.table import Table, TableRow, TableCell, TableColumn
from odf.text import P
doc = load("demo_18.ods")
lines = {}
for style in doc.automaticstyles.getElementsByType(Style):
if style.getAttribute("family") != "table-cell":
continue
sides = {}
for props in style.getElementsByType(TableCellProperties):
for (_, key), value in props.attributes.items():
if key.startswith("border"):
sides[key] = value != "none"
lines[style.getAttribute("name")] = sides
sheet = doc.spreadsheet.getElementsByType(Table)[0]
column_style = []
for column in sheet.getElementsByType(TableColumn):
repeat = int(column.getAttribute("numbercolumnsrepeated") or 1)
column_style += [column.getAttribute("defaultcellstylename")] * repeat
coins = []
names = []
for row in sheet.getElementsByType(TableRow):
values = []
row_names = []
for cell in row.getElementsByType(TableCell):
repeat = int(cell.getAttribute("numbercolumnsrepeated") or 1)
text = "".join(str(p) for p in cell.getElementsByType(P)).strip()
for _ in range(min(repeat, 100)):
values.append(text)
row_names.append(cell.getAttribute("stylename"))
while values and values[-1] == "":
values.pop()
row_names.pop()
if values:
coins.append([int(v) for v in values])
names.append(row_names)
n = len(coins)
def line(i, j, side):
name = names[i][j]
if name is None and j < len(column_style):
name = column_style[j]
sides = lines.get(name, {})
return sides.get("border-" + side, sides.get("border", False))
wall_right = [[line(i, j, "right") or (j + 1 < n and line(i, j + 1, "left")) for j in range(n)] for i in range(n)]
wall_down = [[line(i, j, "bottom") or (i + 1 < n and line(i + 1, j, "top")) for j in range(n)] for i in range(n)]
LOW = -10 ** 9
HIGH = 10 ** 9
high = [[LOW] * n for _ in range(n)]
low = [[HIGH] * n for _ in range(n)]
high[0][0] = coins[0][0]
low[0][0] = coins[0][0]
for i in range(n):
for j in range(n):
if i == 0 and j == 0:
continue
ways_high = []
ways_low = []
if i > 0 and not wall_down[i - 1][j]:
ways_high.append(high[i - 1][j])
ways_low.append(low[i - 1][j])
if j > 0 and not wall_right[i][j - 1]:
ways_high.append(high[i][j - 1])
ways_low.append(low[i][j - 1])
if ways_high:
high[i][j] = max(ways_high) + coins[i][j]
low[i][j] = min(ways_low) + coins[i][j]
answer_max = LOW
answer_min = HIGH
for i in range(n):
for j in range(n):
stop_right = j == n - 1 or wall_right[i][j]
stop_down = i == n - 1 or wall_down[i][j]
if stop_right and stop_down:
answer_max = max(answer_max, high[i][j])
answer_min = min(answer_min, low[i][j])
print(answer_max, answer_min) # 2598 803
Первая часть — чтение: стили ячеек и колонок, числа и имена стилей по строкам, таблицы wall_right и wall_down. Вторая — две таблицы путей high и low: в клетку приходят сверху или слева, если там нет стены, и берут наибольшее или наименьшее из возможного плюс монету. Третья — обход всех угловых клеток. В демо-файле 246 ячеек без собственного стиля наследуют границу колонки; без строки с column_style минимум выходит 762 вместо 803.
На экзамене, где на odfpy рассчитывать нельзя, есть обходной путь: открыть файл в Calc, глядя на экран, вручную составить таблицу стен кодами (например, R — стена справа, D — снизу) и дальше считать динамику по ней. На поле 20 × 20 это пять-семь минут внимательной работы.
Типичные ошибки
Только правый нижний угол
Главная ловушка номера. На демо угол даёт 2553 и 1162 вместо 2598 и 803. Перебирай все угловые клетки.
Стена «в клетке», а не между клетками
Граница справа от клетки закрывает ход вправо из неё, а не вход в неё. Проверяй соседа: вход сверху закрыт, если у верхнего соседа стена снизу; вход слева — если у левого соседа стена справа.
Пропущенная стена в Calc
Одна забытая стена сдвигает значения во всей области правее и ниже. Проверь угловые клетки по экрану: у каждой должна быть стена или край и справа, и снизу.
Заголовок, которого нет
В файле демо первая строка — уже данные. readline для заголовка, оставшийся от учебной формы с заголовком 1..N, выбросит первую строку поля.
Перепутаны строка и столбец
coins[i][j]: первый индекс — строка, второй — столбец. Угловая клетка «14, 11» — четырнадцатая строка, одиннадцатый столбец.
Подборка ошибок по всем номерам — в статье Типичные ошибки на ЕГЭ по информатике.
Тайминг на экзамене
| Этап | Время |
|---|---|
| Открыть файл, найти стены и угловые клетки | 2 мин |
| Таблица максимума в Calc или код на Python | 3–4 мин |
| Таблица минимума, обход угловых клеток | 2 мин |
| Итого | 7–8 мин |
Спецификация отводит восемь минут — ровно столько и уходит. Экономят время заготовленный шаблон и привычка сразу выписать все угловые клетки.
Как тренироваться
- Реши типовой пример 4 × 4 руками — 41 и 10 — и ту же сетку в Calc и на Python.
- Пять заданий с несколькими угловыми клетками; каждый раз сначала выпиши угловые клетки, потом считай.
- Одно задание посчитай только по углу и сравни с ответом — ловушка запомнится.
- Отработай выписывание стен кодами на одном файле и засеки время — на экзамене, где на odfpy рассчитывать нельзя, это путь для Python; чтение границ через
odfв кабинете должно давать ту же таблицу стен.
Как изменились остальные номера — в обзоре ЕГЭ по информатике 2027: что изменилось; демозадание в контексте варианта — в разборе демоверсии 2027. Та же динамика по сетке — в обзоре динамического программирования на ЕГЭ; файлы .ods встречаются и в задании 9, и в задании 22.
Короткий итог
Задание 18 в 2027 году — один лист, стены границами ячеек и несколько угловых клеток. Две таблицы путей, максимум и минимум, и обход всех клеток, где справа и снизу стена или край. На демо — 2598 и 803, а правый нижний угол даёт 2553 и 1162: смотреть только на него — потерять балл.
Задания 18 в форме демоверсии с автопроверкой есть в TuteMe: стены нарисованы границами, угловых клеток несколько, и ни максимум, ни минимум не лежат в правом нижнем углу.