Задание 19 ЕГЭ по информатике: анализ логической игры

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

Как решать

Игра задаётся позицией — количеством камней в куче или в двух кучах — и списком ходов. Партия заканчивается, когда количество камней достигает порога из условия; выигрывает тот, кто сделал последний ход.

Сначала найдите позиции, из которых игрок выигрывает одним ходом. Для этого достаточно, чтобы самый сильный ход, обычно умножение, довёл количество камней до порога. При ходах +1, +4, ×2 и пороге 50 одним ходом выигрывают все позиции от 25 до 49.

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

Для проверки пишут рекурсивную функцию game(s, m): она возвращает True, если нужный игрок выигрывает не позже чем за m оставшихся ходов. На ходах выигрывающего игрока берётся any — достаточно одного хорошего хода, на ходах соперника all — к выигрышу должны вести все его ходы. Для формулировки «партия возможна» any берётся на всех ходах.

Примеры с решением

Пример 1

Два игрока, Петя и Ваня, играют в игру с одной кучей камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить четыре камня или увеличить количество камней в куче в два раза. Игра завершается, когда в куче становится не менее 50 камней. Победителем считается игрок, сделавший последний ход. В начальный момент в куче было S камней, 1 ≤ S ≤ 49.

Известно, что партия закончилась первым ходом Вани и он выиграл. Найдите наименьшее значение S, при котором такое развитие игры возможно.

Проверка ответа на Python

from functools import lru_cache


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


@lru_cache(None)
def possible(s, m):
    """Можно ли закончить игру ровно за m ходов, если оба игрока ходят как угодно."""
    if s >= 50:
        return m == 0
    if m == 0:
        return False
    return any(possible(x, m - 1) for x in moves(s))


# Ваня выиграл первым ходом: игра закончилась ровно на втором ходе партии.
print(min(s for s in range(1, 50) if possible(s, 2)))

Ответ: 13

Ваня выигрывает одним ходом из позиций от 25 до 49: удвоение даёт не меньше 50. Петя должен своим ходом попасть в этот промежуток и не закончить игру. Наименьшее S, из которого это возможно, — 13: удвоение даёт 26. Из 12 Петя получает не больше 24, и Ваня одним ходом выиграть не может.

Пример 2

Петя и Ваня играют с двумя кучами камней, ходят по очереди, начинает Петя. За один ход можно добавить два камня в любую из куч или удвоить количество камней в одной из куч. Игра заканчивается, когда в двух кучах вместе оказывается 81 камень или больше; выигрывает тот, кто сделал последний ход. Сначала в первой куче 6 камней, во второй — S камней, 1 ≤ S ≤ 74.

Укажите минимальное значение S, при котором Петя не может выиграть первым ходом, но при любом ходе Пети Ваня выигрывает своим первым ходом.

Проверка ответа на Python

from functools import lru_cache


def moves(p):
    a, b = p
    return [(a + 2, b), (a, b + 2), (a * 2, b), (a, b * 2)]


@lru_cache(None)
def game(p, m):
    """True, если тот, кому нужно выиграть, выигрывает не позже чем за m оставшихся ходов."""
    if sum(p) >= 81:
        return m % 2 == 0
    if m == 0:
        return False
    h = [game(x, m - 1) for x in moves(p)]
    return any(h) if (m - 1) % 2 == 0 else all(h)


# m = 2: ходит Петя, а выиграть должен Ваня своим первым ходом при любом ходе Пети.
print(min(s for s in range(1, 75) if game((6, s), 2)))

Ответ: 37

Самый сильный ход — удвоение большей кучи. При S = 37 Петя получает не больше 6 + 74 = 80 и выиграть не может. После любого его хода Ваня выигрывает: из (8, 37) удвоением второй кучи получает 82 камня, из (6, 39) — 84, из (12, 37) — 86, из (6, 74) добавлением двух камней — 82. При S = 36 и меньше у Пети есть ход, после которого Ваня сразу не выигрывает: например, из (8, 36) Ваня набирает не больше 8 + 72 = 80.

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

Потренироваться на тренажёре

Частые вопросы

Чем задание 19 отличается от заданий 20 и 21?

Все три задания используют одну игру. В задании 19 разбирают партию в один-два хода, в задании 20 ищут позиции, где Петя выигрывает вторым ходом при любой игре Вани, в задании 21 — позиции, где Ваня выигрывает первым или вторым ходом, но не может обеспечить себе выигрыш первым.

Нужна ли программа для задания 19?

Спецификация не требует специальных программ для этого задания, и его решают рассуждением за несколько минут. Программа из примеров пригодится для проверки и для заданий 20 и 21.

Официальные материалы

Другие задания

Все задания и структура экзамена — на странице ЕГЭ по информатике. Соседние разборы: задание 18 и задание 20.

Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.