Пример 1
Два игрока, Петя и Ваня, играют в игру. Перед ними лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход можно добавить в кучу один камень, добавить четыре камня или увеличить количество камней в два раза. Игра завершается, когда в куче становится не менее 45 камней. Победителем считается игрок, сделавший последний ход. В начальный момент в куче S камней, 1 ≤ S ≤ 44.
Найдите минимальное значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, которая гарантированно позволит выиграть первым ходом.
Показать решение и ответ
1. Нужно S, при котором любой ход Пети ведёт в позицию, выигрышную для Вани за 1 или 2 хода, и хотя бы один ход — в позицию, где Ваня выигрывает только вторым ходом.
2. Позиции, где ходящий выигрывает первым ходом: 23–44. Вторым ходом (из задания 20): 11, 18, 21.
3. Перебираем S по возрастанию. S = 17: ходы 18, 21, 34. 18 и 21 — Ваня выигрывает вторым ходом, 34 — первым. Подходит.
4. Меньшие S не подходят. При S < 17 ход «+1» даёт кучу не больше 17, и среди таких куч выигрышная для Вани только 11 (это S = 10). Но из 10 ход «+4» даёт 14 — оттуда Ваня за два хода не выигрывает.
5. Ответ: 17.
Проверка программой (функция 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(min(s for s in range(1, 45) if game(s) == 'L2')) # Ваня выигрывает первым или вторым ходом, но не гарантированно первым: 17Ответ: 17