Задание 20 ЕГЭ по информатике: выигрыш вторым ходом

Условие игры

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

Задание 20: найдите два значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть вторым ходом независимо от того, как будет ходить Ваня.

Разбор

Позиции от 15 до 28 выигрышны одним ходом. Проигрышная позиция для того, кто ходит: любой ход ведёт в 15–28. Это S = 14: ходы дают 15 и 28.

Программа

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

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

f(s, 3) значит, что Петя выигрывает не более чем за два своих хода (три хода всего), а not f(s, 1) исключает выигрыш первым ходом.

Проверь себя

• Почему S = 14 проигрышная для того, кто ходит? Ответ: любой ход, 15 или 28, даёт сопернику победу одним ходом.
• Выигрывает ли Петя вторым ходом при S = 12? Ответ: нет, его ходы дают 13 и 24, оба не проигрышные для Вани.

Где теряют балл

• Не все ходы Вани. Стратегия Пети должна работать при любом ответе Вани.
• Формат ответа. Значения записываются по возрастанию через пробел, как требует условие.

Как тренироваться

Начало игры в разборе задания 19, продолжение в задании 21. Все номера экзамена в статье ЕГЭ по информатике по номерам.

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