ЕГЭ по информатике 2026, задание 19: игра: один ход

Задания 19, 20 и 21 — одна игра. Меняется вопрос. Задание 19 — базовое, 1 балл. Обычно спрашивают наименьшее значение S, при котором первый игрок не выигрывает сразу, но второй своим первым ходом уже выигрывает при любом ответе первого. Точная формулировка каждый год чуть разная, её надо прочитать до раскраски позиций.

Игроков чаще называют Петя и Ваня. Петя ходит первым. Ходы заданы: добавить 1, умножить на 2, убрать камни и так далее. Игра кончается, когда количество камней стало не меньше N или когда ход невозможен. Победитель — кто сделал последний ход, если не сказано иначе. Две кучи встречаются так же часто, как одна.

Конспект

Не ищите «красивое» S. Разметьте позиции.

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

Для задания 19 обычно нужна самая короткая стратегия:

• позиция, из которой можно сразу завершить игру, — победа за один ход;
• позиция, из которой любой ход отдаёт сопернику такую победу, а своего немедленного выигрыша нет, — то, что часто спрашивают в №19.

Выпишите все S в рабочем диапазоне, не только минимум. Задания 20 и 21 используют ту же разметку. Если разобрать 19 заново для каждого номера, легко разойтись в правилах.

Две кучи: позиция — пара (a, b). Не забывайте, что ход делается в одной куче, если так сказано. Симметрия (a, b) и (b, a) есть не всегда, потому что вопрос может про наименьшую сумму.

Шаблон на Python

Один параметр S, ходы «+1» и «*2», конец при S ≥ 129. Функция возвращает, выигрывает ли текущий игрок. Для №19 отдельно собраны позиции с немедленной победой и позиции, где любой ход ведёт в немедленную победу соперника.

GOAL = 129

def moves(s):
    return [s + 1, s * 2]

win1 = {s for s in range(1, GOAL) if any(m >= GOAL for m in moves(s))}

def is_19(s):
    if s in win1:
        return False
    return all(m in win1 for m in moves(s))

print([s for s in range(1, GOAL) if is_19(s)])

Подставьте ходы и конец партии из условия. Если кучи две, s замените на кортеж и генерируйте ходы по каждой куче.

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

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