Пример 1
Два игрока, Петя и Ваня, играют в игру. Перед ними лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход можно добавить в кучу один камень, добавить четыре камня или увеличить количество камней в два раза. Игра завершается, когда в куче становится не менее 45 камней. Победителем считается игрок, сделавший последний ход. В начальный момент в куче S камней, 1 ≤ S ≤ 44.
Найдите три значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в порядке возрастания.
Показать решение и ответ
1. Петя выигрывает вторым ходом, если может первым ходом получить кучу, из которой Ваня проигрывает при любом ходе. Из задания 19 такая куча одна — 22.
2. Ищем S < 22, из которых одним ходом получается 22: S + 1 = 22 → 21; S + 4 = 22 → 18; S · 2 = 22 → 11.
3. Проверяем, что ни из одного из них Петя не выигрывает первым ходом: максимум 21 · 2 = 42 < 45.
4. Ответ: 11, 18, 21.
Проверка программой (функция game из задания 19):
from functools import lru_cache # запоминаем уже посчитанные позиции, иначе перебор очень долгий
def moves(s): # все ходы из позиции s
return [s + 1, s + 4, s * 2] # +1 камень, +4 камня, удвоение
@lru_cache(None) # кэш результатов для каждой позиции
def game(s): # итог позиции для того, кто сейчас ходит
if s >= 45: # игра уже окончена — ходящий проиграл
return 'L0' # L0: проигрыш «за 0 ходов соперника»
res = [game(t) for t in moves(s)] # итоги позиций после каждого нашего хода (для соперника)
lose = [r for r in res if r[0] == 'L'] # ходы, после которых соперник проигрывает
if lose: # такой ход есть — мы выигрываем
return 'W' + str(min(int(r[1:]) for r in lose) + 1) # побеждаем как можно быстрее
return 'L' + str(max(int(r[1:]) for r in res)) # все ходы плохие — проигрываем как можно позжеОбозначения: W1 — ходящий выигрывает первым ходом, W2 — вторым; L1 — соперник выигрывает своим первым ходом при любом ходе ходящего, L2 — первым или вторым.
print([s for s in range(1, 45) if game(s) == 'W2']) # Петя выигрывает ровно вторым ходом: [11, 18, 21]Ответ: 11 18 21