ЕГЭ · ЗАДАНИЕ 21
Игры: стратегия Вани · практика 17
Одна куча содержит S камней, 1≤S<72. Первый ход делает Петя. За ход можно добавить 1 камень(я) или удвоить кучу. Побеждает тот, кто первым получает не менее 72 камней. Найдите все S, при которых Ваня может гарантировать победу своим первым или вторым ходом при любой игре Пети, но не может гарантировать победу своим первым ходом. Запишите S по возрастанию через пробел.
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 33
Решение по шагам
- Выпишем ходы из позиции s: s+1 и 2s. Достижение 72 камней сразу завершает игру.
- W1: есть ход, сразу достигающий цели. L1: немедленно выиграть нельзя, и каждый ход отдаёт сопернику W1. W2: нет победы за один ход, но есть ход в L1.
- В №21 все ходы Пети должны передавать Ване W1 или W2. Исключаем L1: иначе Ваня гарантировал бы победу уже первым ходом.
- Проверяем все S от 1 до 71. Все подходящие S: 33.
| S | После +1 | После ×2 |
|---|---|---|
| 33 | 34 | 66 |
Проверка на Python
T = 72
def moves(s): return (s + 1, 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 l2(s)]
print(*result)