Для игры, описанной в предыдущем задании, найдите минимальное и максимальное значения при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход и Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.
Решение руками
Рассмотрим Первым ходом Петя достигнет позиции
из которой Ваня не сможет сделать никаких ходов, кроме утроения, что приведёт Петю в позицию
из которой он победит утроением. Теперь рассмотрим
Первым ходом Петя сходит в позицию
из которой Ваня сможет сходить лишь в
из которой Петя победит также утроением.
Решение программой
from functools import lru_cache
def moves(heap):
m = []
if (heap + 1) % 2 != 0:
m += [heap + 1]
if (heap + 3) % 2 != 0:
m += [heap + 3]
if (heap * 3) % 2 != 0:
m += [heap * 3]
return m
@lru_cache(None)
def game(heap):
if heap >= 63:
return ’END’
elif any(game(x) == ’END’ for x in moves(heap)):
return ’WIN1’
elif all(game(x) == ’WIN1’ for x in moves(heap)):
return ’LOSE1’
elif any(game(x) == ’LOSE1’ for x in moves(heap)):
return ’WIN2’
elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
return ’LOSE2’
for s in range(1, 63):
if game(s) == ’WIN2’:
print(s)