ЕГЭ по информатике 2026, задание 23: количество программ

Задание 23 — повышенный уровень, 1 балл. Исполнитель умеет несколько команд, например прибавить 1, прибавить 2, умножить на 2. Нужно число программ, которые переводят число A в число B. Иногда траектория обязана пройти через заданное число или не может его содержать.

ФИПИ не советует выписывать все пути. Их слишком много, и легко пропустить ветку. Рабочий способ — рекуррентная формула: сколькими способами можно получить текущее число из предшественников.

Конспект

Пусть f(x) — число способов получить x из старта.

• f(start) = 1, одна пустая программа;
• f(x) = 0, если x недостижимо или запрещено;
• если в x можно прийти командой из y, то к f(x) прибавляют f(y).

Для команд +1 и *2 удобнее идти от старта и раскидывать способы вперёд:

• из x команда +1 добавляет f(x) к f(x+1);
• команда *2 добавляет f(x) к f(x*2).

Запрещённое число обнуляют и не распространяют из него способы. Обязательная точка M: ответ равен f(M) * g(B), где f — способы от старта до M, g — способы от M до финиша уже без повторного запрета на M. Нельзя просто посчитать пути от старта до B и вычесть пути мимо M, если не уверены в формуле. Произведение двух задач проще.

Если команды только увеличивают число, идти нужно в сторону роста и не заходить далеко за B. Команда вычитания требует другой порядок, от больших к меньшим, либо рекурсию с кэшем.

Команды «приписать цифру» превращают число в другое десятичное. Тогда предшественников ищут разбором, а не только x-1.

Шаблон на Python

start, goal = 1, 20
must = 8          # поставьте None, если обязательной точки нет
banned = {15}

def ways(a, b, forbid):
    f = [0] * (b + 1)
    if a <= b:
        f[a] = 1
    for x in range(a, b + 1):
        if x in forbid or f[x] == 0:
            f[x] = 0
            continue
        for nxt in (x + 1, x + 2, x * 2):
            if nxt <= b and nxt not in forbid:
                f[nxt] += f[x]
    return f[b]

if must is None:
    print(ways(start, goal, banned))
else:
    # команды только увеличивают число, поэтому в must повторно не заходят
    print(ways(start, must, banned) * ways(must, goal, banned))

Во второй задаче от M до цели саму точку M не запрещайте, иначе f(M) обнулится. Запрет на повторный заход в M нужен только если по условию через неё проходят ровно один раз и команды могут вернуться. При только увеличивающих командах вернуться нельзя, достаточно произведения.

В строке шаблона с banned | {must} if False запрет на M после старта не включается. Оставьте так для команд, которые не умеют вернуться. Если в варианте есть вычитание, запретите повторный вход явно.

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

• Пути через обязательную точку посчитаны как все пути до цели.
• Запрещённое число осталось транзитом: из него продолжили раскидывать способы.
• Команда *2 применена к нечётному «делению», когда шли назад, и получили нецелые.
• Выписали полсотни траекторий и сбились на одной развилке.