Задание 20 ЕГЭ по информатике: Петя выигрывает вторым ходом — разбор и примеры

Задание 20 продолжает игру из задания 19: та же куча камней, те же ходы, тот же порог окончания. Теперь вопрос сложнее: найти такие начальные позиции, в которых Петя не может выиграть первым ходом, но может выиграть своим вторым ходом при любой игре Вани. Обычно таких значений два или три, и их нужно записать в порядке возрастания. Ключ к заданию — понять, через какие позиции проходит выигрышная стратегия Пети.

Что проверяет задание

• умение строить выигрышную стратегию — правило ходов, которое ведёт к победе при любых ответах соперника;
• понимание типов позиций: В1 (ходящий выигрывает одним ходом), П1 (любой ход ходящего даёт сопернику выигрыш одним ходом), В2 (ходящий выигрывает вторым ходом, но не первым);
• аккуратность: нужно найти все подходящие значения, а не одно.

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

Типичные формулировки

1. «Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход и может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Запишите их в порядке возрастания».
2. То же для двух куч: первая куча фиксирована, вторая — S камней.
3. Иногда значений три, и формулировка просит «все такие значения» или «минимальное и максимальное».

Пошаговый метод

1. Найдите позиции В1. Все s, из которых один ход даёт не меньше цели.
2. Найдите позиции П1. Это s, не входящие в В1, у которых каждый ход ведёт в В1. Обычно П1 — одно-два значения прямо под границей В1.
3. Найдите позиции В2. Это s, не входящие в В1, у которых есть ход в П1.
4. Выпишите все В2 в нужном диапазоне по возрастанию — это и есть ответ.
5. Проверьте каждое значение «руками»: укажите ход Пети в П1 и убедитесь, что все ответы Вани ведут в В1.

Разбор примера

Игра та же, что в разборе задания 19. Ходы: добавить 1 камень, добавить 4 камня, удвоить кучу. Игра заканчивается, когда в куче не меньше 57 камней. Начальное количество S от 1 до 56, первым ходит Петя. Найдите все значения S, при которых Петя не может выиграть первым ходом, но выигрывает своим вторым ходом при любой игре Вани.

Шаг 1. В1. Удвоение даёт победу при 2s ≥ 57, то есть s ≥ 29. Значит, В1 — это s от 29 до 56.

Шаг 2. П1. Ищем s ≤ 28, у которых все три хода (s + 1, s + 4, 2s) попадают в В1, то есть не меньше 29. Самый маленький ход — s + 1, поэтому нужно s + 1 ≥ 29, то есть s = 28. Проверка: 28 → 29, 32, 56 — все в В1, а сам 28 в В1 не входит (56 < 57, 32 < 57). Значит, П1 = {28}.

Шаг 3. В2. Ищем s ≤ 28, s ≠ 28, у которых есть ход ровно в 28:

• s + 1 = 28 даёт s = 27;
• s + 4 = 28 даёт s = 24;
• 2s = 28 даёт s = 14.

Все три значения не входят в В1 (их удвоение меньше 57), поэтому каждое из них — позиция В2.

Шаг 4. Проверка одного значения. S = 24: Петя делает ход 24 → 28. Ваня может получить 29, 32 или 56, и в каждом случае Петя удваивает кучу: 58, 64 или 112 — победа вторым ходом. Выиграть первым ходом Петя не мог: максимум 2 · 24 = 48 < 57.

Ответ: 14, 24, 27 (в порядке возрастания). Если бы формулировка просила два значения, а получилось три, это сигнал перепроверить перенос условия: в реальных вариантах число значений в формулировке всегда совпадает с правильным ответом.

Код на Python

Шаблон тот же, что в заданиях 19 и 21: функция классифицирует позицию, выигрывающий стремится выиграть быстрее, проигрывающий — затянуть игру.

from functools import lru_cache

GOAL = 57

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

@lru_cache(None)
def result(s):
    nxt = moves(s)
    if any(x >= GOAL for x in nxt):
        return ('W', 1)
    res = [result(x) for x in nxt]
    lose = [k for t, k in res if t == 'L']
    if lose:
        return ('W', min(lose) + 1)
    return ('L', max(k for t, k in res))

# Задание 20: позиции типа В2
print([s for s in range(1, GOAL) if result(s) == ('W', 2)])   # [14, 24, 27]

Запись ('W', 2) означает ровно то, что требует условие: выиграть первым ходом нельзя (иначе было бы ('W', 1)), а вторым — можно при любой игре соперника. Для двух куч замените позицию на кортеж и перепишите moves.

Как проверить ответ без программы

Даже если ответ получен программой, полезно убедиться в нём вручную — это занимает минуту. Для каждого найденного значения запишите короткую «цепочку»: ход Пети, все возможные ответы Вани и выигрывающий ход Пети после каждого из них. Например, для S = 14: Петя удваивает кучу и получает 28; Ваня делает 29, 32 или 56; Петя удваивает и получает не меньше 57. Если для какого-то ответа Вани выигрывающего хода не нашлось, значит, позиция после хода Пети не П1 и значение нужно исключить. Такая запись заодно помогает при решении задания 21: позиции В2 понадобятся там как промежуточные.

Частые ошибки

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

Потренируйтесь

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