Задание 18 — это задача оптимизации на таблице: поле-лабиринт, в каждой клетке число, исполнитель идёт по разрешённым командам и собирает числа. В 2027 году задание относится к разделу «Информационные технологии», стоит 1 первичный балл, а ответ — два целых числа.
Минимум для задания 18
находить стартовую и конечную клетки
различать внешние и внутренние стены
определять конечные (угловые) клетки
выписывать разрешённые команды и смещения
задавать стартовое значение динамики
учитывать стены при переходе
считать максимум и минимум отдельно
собирать ответ по всем конечным клеткам
заменять вес клетки при изменённых правилах
проверять порядок двух чисел в ответе
Поле, старт и финиш
Поле — квадрат N×N (в некоторых вариантах прямоугольная таблица; обычно N от 10 до 30). В каждой клетке записано число: монета, бонус, плата, высота или заряд. Исполнитель за один ход перемещается по командам условия. Число посещённой клетки добавляется к счёту; стартовая и конечная клетки тоже учитываются, если в условии не сказано иначе.
Старт может быть в любом углу, а не только в левом верхнем.
Финиш может быть один (правый нижний угол) или несколько «угловых» клеток.
Путь монотонный: назад и по кругу обычно ходить нельзя.
Числа могут быть отрицательными — тогда «максимум» и «минимум» особенно важно не перепутать.
Если в условии сказано «из любой левой клетки», стартов несколько.
Стены и запрещённые клетки
Стена — это утолщённая линия между клетками или по границе поля. Переход через неё запрещён. Иногда запрет задан не линией, а цветом клетки, значением 0 или диапазоном 101–499.
Проверяйте стену со стороны той клетки, из которой идёт ход.
Внешняя граница тоже стена: за пределы поля выходить нельзя.
Стена справа от (i, j) запрещает переход (i, j) → (i, j+1).
Стена снизу от (i, j) запрещает переход (i, j) → (i+1, j).
Запрещённую клетку удобно считать недостижимой: dp = None или −∞/+∞.
Динамика по клеткам
Главная идея: лучший результат в клетке зависит только от лучших результатов в клетках, из которых в неё можно прийти. Для команд «вправо» и «вниз» это верхний и левый соседи. Для минимума нужна отдельная копия таблицы: значения максимума не равны значениям минимума, поэтому таблицу нужно пересчитать с MIN.
Если сверху стена, верхний сосед не рассматривается.
Если слева стена, левый сосед не рассматривается.
Если оба перехода запрещены, клетка недостижима.
Для минимума нельзя инициализировать нулём: ноль может оказаться «лучше» реального пути.
dp_max[i][j] = a[i][j] + max(dp_max[i-1][j], dp_max[i][j-1])dp_min[i][j] = a[i][j] + min(dp_min[i-1][j], dp_min[i][j-1])dp[0][0] = a[0][0]недостижимо: −∞ для максимума, +∞ для минимума
Порядок обхода
Формулы работают, только если к моменту обработки клетки все её предшественники уже посчитаны. Порядок зависит от команд.
«вправо/вниз»: строки сверху вниз, внутри строки слева направо.
«влево/вниз»: строки сверху вниз, внутри строки справа налево.
«вверх/вправо»: строки снизу вверх, внутри строки слева направо.
«вверх/влево»: строки снизу вверх, внутри строки справа налево.
Если направлений несколько, ориентируйтесь на то, что все предшественники должны быть раньше.
В формулировке «угловые клетки, справа и снизу ограниченные стенами» финишей может быть несколько. Это не только правый нижний угол: любая клетка, из которой нельзя пойти вправо и вниз, даёт итоговую сумму.
Сначала отметьте все такие клетки, затем считайте динамику по всему полю.
Максимум и минимум берите по значениям во всех конечных клетках.
Если в условии прямо сказано «в правую нижнюю клетку», финиш один.
Для «Коня» или «Попрыгуна» конечная клетка — та, из которой нет ни одного разрешённого хода.
Не отбрасывайте конечную клетку только потому, что она не в правом нижнем углу.
Максимум и минимум
Это две независимые задачи. Их удобно решать на двух копиях листа или двумя массивами в программе.
Сначала заполните таблицу для максимума, сохраните ответ.
Затем сделайте копию и замените МАКС на МИН (или max на min).
Не меняйте функцию в уже заполненной таблице без копии — потеряете максимум.
Для минимума проверяйте, что путь вообще существует.
В ответе сначала то число, которое просят первым: часто «максимум, затем минимум», но бывает и наоборот.
Изменённые правила сбора
В основе почти всех вариантов — та же динамика. Меняется только вес клетки или условие перехода.
Удвоенный номинал: w = 2·a[i][j].
Чётное — удвоить, нечётное — половина: w = 2x при x % 2 == 0, иначе x // 2.
Произведение номинала на число вхождений: w = x · count(x).
Энергия: старт — a[0][0], шаг вправо вычитает число целевой клетки, шаг вниз — ceil(число целевой клетки / 2).
Обязательная клетка: считайте путь старт → клетка и клетка → финиш отдельно.
Заправки: храните в динамике запас энергии, а не только сумму.
Шаг зависит от числа в текущей клетке: для каждого состояния перебирайте только разрешённые смещения (№ 29454).
Excel или программа
Оба способа допустимы. В Excel удобно видеть разметку стен, в программе — автоматически обрабатывать сложные правила и проверять себя.
Excel: формулы МАКС/МИН, относительные ссылки, заливка клеток по типу перехода.
Excel: для стен вручную уберите запрещённого соседа из формулы.
Python: openpyxl для .xlsx, pandas.read_excel(..., engine='odf') для .ods.
Python: стены читайте из cell.border или задавайте матрицей запретов.
Проверка: пройдите найденный маршрут вручную и сложите числа.
Формат ответа
Ответ — два целых числа. В задании 18 почти всегда просят пару «максимум и минимум», но порядок задаётся условием.
Записывайте числа через пробел, без единиц и пояснений.
Если просят «сначала минимальную, затем максимальную» — не переставляйте.
Если в ответе одно число (например, количество маршрутов), не добавляйте второе.
Проверьте, что оба числа целые и не содержат разделителей тысяч.
Разбор примера
Учебный пример: две конечные клетки
Поле 4×4. Старт — левая верхняя клетка, команды — «вправо» и «вниз». Справа и снизу от клетки 1 в первой строке стоят стены, поэтому она тоже конечная. Найдите максимальную и минимальную итоговые суммы.
Монеты в клетках. Стены: справа и снизу от клетки 1 в первой строке.
1
2
3
4
1
2
5
1
9
2
4
8
7
2
3
1
3
9
5
4
7
2
6
8
Значения динамики: максимум / минимум. «—» — клетка недостижима.
1
2
3
4
1
2 / 2
7 / 7
8 / 8
— / —
2
6 / 6
15 / 14
22 / 21
24 / 23
3
7 / 7
18 / 10
31 / 19
36 / 24
4
14 / 14
20 / 12
37 / 18
45 / 26
Отмечаем старт (1,1) и конечные клетки: (1,3) — справа и снизу стены; (4,4) — правый нижний угол.
Заполняем первую строку: 2, 7, 8; в (1,4) перейти нельзя из-за стены справа от (1,3).
Заполняем первый столбец: 2, 6, 7, 14 — здесь ход только сверху.
Для внутренних клеток берём максимум (или минимум) из верхней и левой, прибавляем число клетки. Например, (2,3): сверху мешает стена снизу от (1,3), поэтому 15 + 7 = 22 для максимума и 14 + 7 = 21 для минимума.
В конечных клетках получились 8 и 45 для максимума, 8 и 26 для минимума.
Максимум — 45, минимум — 8. Ответ записываем в порядке условия.
Ответ45 8 — максимальная и минимальная суммы.
Способы решения
Выберите метод под формулировку
Методы собраны по решениям задания 18 из базы Kompege. Начните с того, что именно нужно найти в условии.
01
когда поле до 30×30 и стены видны
Волна формул в Excel
Когда использовать: Классическая задача: старт в углу, команды «вправо» и «вниз», нужно найти максимум и минимум.
Перенесите числа на новый лист и сохраните утолщённые границы — это стены.
Разметьте клетки по числу разрешённых входов: «только сверху», «только слева», «с двух сторон», «недостижима».
В стартовую клетку таблицы результатов запишите число стартовой клетки.
Для «только сверху»: =A2 + A6; для «только слева»: =B1 + A6; для «с двух сторон»: =B2 + МАКС(A7; B6) — подставьте свои адреса.
Протяните формулы на всё поле. Для минимума сделайте копию листа и замените МАКС на МИН через Ctrl+H.
Соберите значения в конечных клетках и возьмите максимум или минимум.
Проверьте ответ, пройдя найденный маршрут вручную.
Пример
Поле 4×4 из демоверсии: 1 8 8 4 / 10 1 1 3 / 1 3 12 2 / 2 3 5 6. Старт (1,1), финиш (4,4), стен нет.
Обходите клетки в порядке движения; для каждой собирайте только допустимых предшественников.
Для максимума берите max(prev), для минимума — min(prev); если предшественников нет, клетка недостижима.
Соберите значения в конечных клетках и выведите ответ в нужном порядке.
Пример
Поле из учебного примера: стены справа и снизу от (0,2), конечные клетки — (0,2) и (3,3).
a = [[2, 5, 1, 9],
[4, 8, 7, 2],
[1, 3, 9, 5],
[7, 2, 6, 8]]
right_wall = {(0, 2)} # стена справа от клетки (0, 2)
down_wall = {(0, 2)} # стена снизу от клетки (0, 2)
finals = [(0, 2), (3, 3)]
def best(maximize=True):
n = len(a)
dp = [[None] * n for _ in range(n)]
dp[0][0] = a[0][0]
for i in range(n):
for j in range(n):
if i == 0 and j == 0:
continue
prev = []
if j > 0 and (i, j - 1) not in right_wall and dp[i][j - 1] is not None:
prev.append(dp[i][j - 1])
if i > 0 and (i - 1, j) not in down_wall and dp[i - 1][j] is not None:
prev.append(dp[i - 1][j])
if prev:
dp[i][j] = a[i][j] + (max(prev) if maximize else min(prev))
values = [dp[i][j] for i, j in finals if dp[i][j] is not None]
return max(values) if maximize else min(values)
print(best(True), best(False)) # 45 8
Ответ45 8.
По мотивам задач № 16706, 17836 и 31034.
03
когда команды не «вправо/вниз»
Другие направления и старт
Когда использовать: Старт в другом углу, команды «влево/вниз», «вверх/вправо» или «вверх/влево».
Определите старт и финиш по тексту условия.
Для каждой команды найдите, из какой стороны приходит исполнитель.
Выберите порядок обхода: для «влево/вниз» — сверху вниз и справа налево.
В формуле оставьте только те предшественники, которые не отделены стеной.
При отражении поля не забудьте отразить и стены.
Соберите ответ в указанном порядке.
Пример
Поле 3×3: 1 2 3 / 4 5 6 / 7 8 9. Команды «влево» и «вниз», старт в правом верхнем углу, финиш в левом нижнем.
# «влево/вниз»: обход сверху вниз, справа налево
for i in range(n):
for j in range(n - 1, -1, -1):
# предшественники: (i, j + 1) и (i - 1, j)
...
ОтветМаксимум 33, минимум 17.
По мотивам задач № 16265, 21114, 2389 и 930.
04
диагональ, прыжок, ход на две клетки
Три и более команд
Когда использовать: Разрешены диагональ, прыжок коня, ход на две клетки или команда зависит от клетки.
Выпишите все команды и смещения: (0,1), (1,0), (1,1), прыжок коня и т. п.
Для клетки переберите все команды; предшественник — клетка минус смещение.
Проверьте, что предшественник внутри поля и переход не перекрыт стеной.
Если команда разрешена только из части клеток, добавьте условие на предшественника.
Обходите клетки так, чтобы предшественники были готовы.
Для «жёлтых» клеток, где разрешена только диагональ, формулы меняются по цвету клетки.
Пример
Поле 3×3: 1 2 3 / 4 5 6 / 7 8 9; команды «вправо», «вниз» и «вправо-вниз»; старт (1,1), финиш (3,3).
prev = []
if i > 0:
prev.append(dp[i - 1][j]) # сверху
if j > 0:
prev.append(dp[i][j - 1]) # слева
if i > 0 and j > 0:
prev.append(dp[i - 1][j - 1]) # по диагонали
dp[i][j] = a[i][j] + (max(prev) if maximize else min(prev))
ОтветМаксимум 29, минимум 15.
По мотивам задач № 2711, 2680, 3081, 3159 и 2162.
05
когда просят не сумму, а число путей
Количество маршрутов
Когда использовать: В условии «количество различных маршрутов», «сколько способов», а не максимум и минимум.
В стартовой клетке поставьте 1.
В каждой клетке сложите числа путей из разрешённых предшественников.
Стена или запрещённая клетка просто не добавляет путей.
Если стартов несколько, поставьте 1 в каждой; если финишей несколько, сложите ответы.
Проверьте, что путь не проходит через запрещённые клетки.
Пример
Поле 3×3 без стен, движение «вправо/вниз», старт (1,1), финиш (3,3).
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1
for i in range(n):
for j in range(n):
if i:
dp[i][j] += dp[i - 1][j]
if j:
dp[i][j] += dp[i][j - 1]
print(dp[-1][-1]) # 6
Ответ6 маршрутов.
По мотивам задач № 13995 и 2156; у № 2156 есть видеоразбор.
06
удвоение, половина, произведение, энергия
Изменённые правила сбора
Когда использовать: Сумма считается не как «число клетки», а по особому правилу; или есть обязательная клетка и заправки.
Выпишите вес клетки w(i,j) по правилу условия.
Подставьте w вместо a в рекуррентную формулу.
Если вес зависит от направления входа, добавьте его в конкретный переход.
Для обязательной клетки считайте два участка и вычтите её число один раз.
Для энергии храните в динамике запас, а не сумму; проверяйте, что ход возможен.
Проверьте, что стартовая клетка обрабатывается по тому же правилу, если условие не делает исключения.
Пример
Поле 2×2: 1 2 / 3 4. Каждая посещённая клетка удваивается, включая старт.
Видеоразборы открытого курса КомпЕГЭ; для заданий 8–12 и 27 — дополнительные разборы демоверсии 2027.
По базе Kompege: 851 задача, 17 решений (все текстовые, часть с изображениями) и 231 видеоразбор (131 YouTube, 63 VK, 37 Rutube) по заданию 18. При подготовке методов использованы решения задач № 9962, 10127, 13995, 14314, 16265, 16706, 17098, 17836, 17983, 22499 и 31034; дополнительно использованы условия и видеоразборы задач № 1971, 3224, 2389, 930, 2711, 2680, 3081, 3159, 2162, 3371, 832, 3896, 470, 583, 1757, 2527, 726, 2126, 2156 и 29454; примеры переработаны в учебные.
Разборы из видео
Задачи, которые разбирают в курсе
Условия и код показаны в кадре в конце соответствующего фрагмента. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие.
№ 3758
разбор из видео · 2027
Робот: максимум и минимум вознаграждения
Квадрат N×N, Робот идёт из правой верхней клетки в левую нижнюю командами влево, вниз и влево-вниз. Найдите максимальное и минимальное вознаграждение; при ходе влево-вниз вознаграждение удваивается.
По одному пункту на каждую главу: условие или код из кадра, ответ и ссылка. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие; номер берётся из кадра. Текст с экрана распознан автоматически, служебные строки и артефакты удалены; если текст нечитаем, остаются название, таймкод и ссылка.
Показать все фрагменты (12)
2027 · 00:00Приветствие
Исполнитель Робот может переме-шаться по клеткам, выполняя 38 одно перемешение одну из двух команл: По команде вправо Робот перемещается в соседнюю правую клетку;
"Исполнитель Робот может перемешаться по клеткам, выполняя за одно. перемещение одну 13 лвух команд: По команде вправо PoGor перемешается в соседнюю правую клетку; по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быль внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Робот забирает монету с собой: это также относится к начальной и конечной В ‹утовых клетках поля — тех, которые справа п снизу ограничены "стенами, Робот не может продолжать движение, поэтому накопленная сумма.
Исполнитель Робот стоит в левом верхнем углу поля, "ралинованного на клетки. Он может перемещаться по клеткам, выполняя за дно перемещение одну пз лвух команд: По команде вправо Робот перемешается в соседнюю правую клетку; по команде вниз — в соседнюю нижнюю. Между соселними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. запуском Робота в каждой клетке квадрата лежит монета достопнством от 1 до 100. Посетив клетку, Робот забирает монету с собой; T 1 к начальной п конечной клеткам маршрута Робота. В угловых клетках "поля — тех, которые справа п снизу ограничены стенами, Робот He может продолжать движение, поэтому накопленная сумма считается итоговой. "TaKIIX конечных клеток на поле может быть несколько, включая правую + нижнюю клетку поля. При разных запусках итоговые накопленные суммы -- В ЕН EL MI
(% 8648) (Демо-2026) Исполнитель Робот стоит в левом верхнем углу поля, разлинованного на клетки. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз — в соседнюю нижнюю. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в кажлой клетке квадрата лежит монета достоинством от 1 Посетив клетку, Робот забирает монету с собой; это также относится к начальной п конечной клеткам маршрута Робота. поля — тех, которые справа п снизу ограничены стенами, Робот не может продо
Определите максимальное 1 минимальное вознаграждение, которое может получить Робот, пройдя из правой верхней клетки в левую нижнюю. ответе укажите два числа — сначала максимальное вознаграждение, затем. Исходные данные для Робота записаны в файле 18-9556 в виде прямоугольной таблипы, каждая ячейка которой соответствует клетке
Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну изтрёх команд: влево, вниз или влево-вниз. По команде влево Робот перемещается в соседнюю левую клетку, по команде вниз в соседнюю — нижнюю, а по команде влево-вниз — на одну клетку влево п вниз по „днагонали. При попытке выхода за границу квадрата Робот разрушается. Tlepext кажлым запуском Робота в каждой клетке квадрата записана величина вознаграждения от 10 100. Попав в клетку после хода влево или вниз, Робот получает указанное в ней вознаграждение, а если он попал в клетку - - после выполнения команды влево-вниз, вознаграждение удваивается. Это также относится к начальной п конечной клетке маршрута Робота. Определите максимальное и минимальное вознаграждение, которое может получить Робот, пройдя из правой верхней клетки в левую нижнюю. В ответе укажите два числа — сначала максимальное вознагражде
"Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну 19 двух команд: По команде вправо Робот перемещается в соседнюю правую клетку. по команде вниз —в "соседнюю нижнюю, В каждой клетке квадрата записано число от 10 0 99. Посетив клетку ¢ нечетным значением, Робот увеличивает счет на 1; иначе "Исходные данные записаны в файле 13-}1.515 в виде электронной таблице размером МХМ, каждая ячейка которой соответствует клетке квадрата. "Определите максимальный п минимальный счёт который может собрать два числа — сначала максимальный счёт, затем минимальный.
Определите минимально возможную денежную сумму. которую может собрать робот и общее количество клеток этого маршруга. "Исходные данные записаны в файле 13-169. в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля.