ЕГЭ · ЗАДАНИЕ 20
Игры: победа Пети вторым ходом · практика 16
Одна куча содержит S камней, 1≤S<68. Первый ход делает Петя. За ход можно добавить 2 камень(я) или удвоить кучу. Побеждает тот, кто первым получает не менее 68 камней. Найдите все S, при которых Петя не может выиграть первым ходом, но может гарантировать победу своим вторым ходом при любой игре Вани. Запишите S по возрастанию через пробел.
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 16 30 31
Решение по шагам
- Выпишем ходы из позиции s: s+2 и 2s. Достижение 68 камней сразу завершает игру.
- W1: есть ход, сразу достигающий цели. L1: немедленно выиграть нельзя, и каждый ход отдаёт сопернику W1. W2: нет победы за один ход, но есть ход в L1.
- В №20 ищем W2: Петя выбирает ход в L1, затем при любом ответе Вани выигрывает.
- Проверяем все S от 1 до 67. Все подходящие S: 16 30 31.
| S | После +2 | После ×2 |
|---|---|---|
| 16 | 18 | 32 |
| 30 | 32 | 60 |
| 31 | 33 | 62 |
Проверка на Python
T = 68
def moves(s): return (s + 2, s * 2)
def w1(s): return s < T and any(x >= T for x in moves(s))
def l1(s): return s < T and not w1(s) and all(w1(x) for x in moves(s))
def w2(s): return s < T and not w1(s) and any(l1(x) for x in moves(s))
def l2(s):
return (s < T and not w1(s) and not l1(s)
and all(w1(x) or w2(x) for x in moves(s)))
result = [s for s in range(1, T) if w2(s)]
print(*result)