ЕГЭ информатика 19-21 задание разбор, теория, как решать.

ЕГЭ Информатика — Полный разбор заданий №19–21 (игры с кучами)

Что решаем? Игры между Петей и Ваней: один или две кучи, добавляем/убираем/умножаем, игра заканчивается по порогу.
Нужно найти стартовые значения, при которых у Пети/Вани есть выигрышная стратегия.

1) Базовая идея

Ходы по очереди, Петя ходит первым.
Победа фиксируется, когда выполнено условие окончания игры (например, s ≥ 51 или s ≤ 19, или a+b ≥ M).
Выигрышная стратегия — игрок гарантированно выигрывает при любых ходах соперника.

2) Универсальный шаблон решения (рекурсия)

def f(s, m):
    # 1. Окончание игры: если порог достигнут, выигрывает тот, кто сделал последний ход
    if ...:                      # например: s >= 51  ИЛИ  s <= 19  ИЛИ  a+b >= 227
        return m % 2 == 0        # True, если последний ход сделал текущий игрок

    # 2. Ходы закончились — победы нет
    if m == 0:
        return 0

    # 3. Все варианты следующего хода
    h = [f(..., m-1), f(..., m-1), ...]

    # 4. Чей ход:
    # - если следующий ход делает Петя → ищем ЛЮБОЙ удачный ход (any)
    # - если следующий ход делает Ваня → он мешает, значит нужны ВСЕ удачные ходы (all)
    return any(h) if (m-1) % 2 == 0 else all(h)

def f(s, m):

# 1. Окончание игры: если порог достигнут, выигрывает тот, кто сделал последний ход

if ...: # например: s >= 51 ИЛИ s <= 19 ИЛИ a+b >= 227

return m % 2 == 0 # True, если последний ход сделал текущий игрок

# 2. Ходы закончились — победы нет

if m == 0:

return 0

# 3. Все варианты следующего хода

h = [f(..., m-1), f(..., m-1), ...]

# 4. Чей ход:

# - если следующий ход делает Петя → ищем ЛЮБОЙ удачный ход (any)

# - если следующий ход делает Ваня → он мешает, значит нужны ВСЕ удачные ходы (all)

return any(h) if (m-1) % 2 == 0 else all(h)

Где:

• s — состояние (одна куча); для двух куч используйте f(a, b, m);

• m — сколько ходов осталось до проверки условия (2 — для №19, 3 — для №20, 4 — для №21).

Особый случай: «после неудачного первого хода Пети»

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

# Быстрый вариант:
return any(h)   # вместо any(...)/all(...)
# или явно:
return any(h) if (m-1) % 2 == 0 else any(h)

# Быстрый вариант:

return any(h) # вместо any(...)/all(...)

# или явно:

return any(h) if (m-1) % 2 == 0 else any(h)

3) Три типовых модели задач

Тип 1. Одна куча — «добавляем» (порог сверху)

Пример условия: за ход можно +1, +4 или ×2; игра заканчивается при s ≥ 51.

Код-шаблон

def f(s, m):
    if s >= 51:               # окончание игры
        return m % 2 == 0
    if m == 0:
        return 0
    h = [f(s + 1, m - 1), f(s + 4, m - 1), f(s * 2, m - 1)]
    return any(h) if (m - 1) % 2 == 0 else all(h)

print('19)', [s for s in range(1, 51) if f(s, 2)])
print('20)', [s for s in range(1, 51) if not f(s, 1) and f(s, 3)])
print('21)', [s for s in range(1, 51) if not f(s, 2) and f(s, 4)])

def f(s, m):

if s >= 51: # окончание игры

return m % 2 == 0

if m == 0:

return 0

h = [f(s + 1, m - 1), f(s + 4, m - 1), f(s * 2, m - 1)]

return any(h) if (m - 1) % 2 == 0 else all(h)

print('19)', [s for s in range(1, 51) if f(s, 2)])

print('20)', [s for s in range(1, 51) if not f(s, 1) and f(s, 3)])

print('21)', [s for s in range(1, 51) if not f(s, 2) and f(s, 4)])

Пример ответа

19) [25]
20) [21, 24]
21) [20, 23]

19) [25]

20) [21, 24]

21) [20, 23]

Тип 2. Две кучи — «добавляем/умножаем» (порог по сумме)

Пример условия: за ход можно увеличить любую кучу на 1 или умножить на 2; игра заканчивается при a + b ≥ 227. Вторая куча фиксирована в условии, например b = 17.

Код-шаблон

def f(a, b, m):
    if a + b >= 227:
        return m % 2 == 0
    if m == 0:
        return 0
    h = [
        f(a + 1, b, m - 1),
        f(a, b + 1, m - 1),
        f(a * 2, b, m - 1),
        f(a, b * 2, m - 1),
    ]
    return any(h) if (m - 1) % 2 == 0 else all(h)

print('19)', [s for s in range(1, 210) if f(s, 17, 2)])
print('20)', [s for s in range(1, 210) if not f(s, 17, 1) and f(s, 17, 3)])
print('21)', [s for s in range(1, 210) if not f(s, 17, 2) and f(s, 17, 4)])

def f(a, b, m):

if a + b >= 227:

return m % 2 == 0

if m == 0:

return 0

h = [

f(a + 1, b, m - 1),

f(a, b + 1, m - 1),

f(a * 2, b, m - 1),

f(a, b * 2, m - 1),

]

return any(h) if (m - 1) % 2 == 0 else all(h)

print('19)', [s for s in range(1, 210) if f(s, 17, 2)])

print('20)', [s for s in range(1, 210) if not f(s, 17, 1) and f(s, 17, 3)])

print('21)', [s for s in range(1, 210) if not f(s, 17, 2) and f(s, 17, 4)])

Пример ответа

19) [53, 54, 55, 56...]
20) [96, 104]
21) [95, 103]

19) [53, 54, 55, 56...]

20) [96, 104]

21) [95, 103]

Тип 3. Одна куча — «убавляем/делим» (порог снизу)

Пример условия: за ход можно −2, −5, либо // 3; игра заканчивается при s ≤ 19.

Код-шаблон

def f(s, m):
    if s <= 19:
        return m % 2 == 0
    if m == 0:
        return 0
    h = [f(s - 2, m - 1), f(s - 5, m - 1), f(s // 3, m - 1)]
    return any(h) if (m - 1) % 2 == 0 else all(h)

print('19)', [s for s in range(20, 1000) if f(s, 2)])
print('20)', [s for s in range(20, 1000) if not f(s, 1) and f(s, 3)])
print('21)', [s for s in range(20, 1000) if not f(s, 2) and f(s, 4)])

def f(s, m):

if s <= 19:

return m % 2 == 0

if m == 0:

return 0

h = [f(s - 2, m - 1), f(s - 5, m - 1), f(s // 3, m - 1)]

return any(h) if (m - 1) % 2 == 0 else all(h)

print('19)', [s for s in range(20, 1000) if f(s, 2)])

print('20)', [s for s in range(20, 1000) if not f(s, 1) and f(s, 3)])

print('21)', [s for s in range(20, 1000) if not f(s, 2) and f(s, 4)])

Пример ответа

19) [60, 61]
20) [62, 63, 65, 66, 180, 181, 182, 183, 184, 185]
21) [64, 67, 68, 186, 187]

19) [60, 61]

20) [62, 63, 65, 66, 180, 181, 182, 183, 184, 185]

21) [64, 67, 68, 186, 187]

4) Как читать результаты для №19–21

Номер	Логика в коде	Смысл
19	`f(s, 2)` или `f(a,b,2)`	Петя выигрывает своим первым ходом (за 1 ход).
20	`not f(..., 1) and f(..., 3)`	Петя не выигрывает сразу, но выигрывает вторым ходом независимо от Вани.
21	`not f(..., 2) and f(..., 4)`	У Вани нет гарантии победы первым/вторым ходом, но у Пети есть к 4-му ходу.

5) Быстрые правила и лайфхаки

Если в условии «после неудачного первого хода Пети» — замените all на any для обоих игроков (или просто верните any(h)).
Порог сверху: s ≥ N или a + b ≥ N; порог снизу: s ≤ N.
Для двух куч всегда проверяем по сумме, если так сказано в условии.
Номера задач → глубина:
№19 → m = 2, №20 → m = 3, №21 → m = 4.
Диапазон перебора начальных значений: берите разумные границы из условия (например, 1..50 или 1..210).