Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, увеличить количество камней в куче в два раза, увеличить количество камней в куче в три раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 
. Если при этом в куче оказалось не более 
камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было 
камней, 
.
Найдите минимальное значение 
, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
Решение БУ
from functools import lru_cache
@lru_cache(None)
def game(first_heap): # Функция игры
if first_heap > 72: # Если камней в куче стало более 72
return 1 # Возвращаем 1, означающую победу Вани "первым ходом" из-за плохого хода Пети
if first_heap >= 43: # Если камней в куче стало не менее 43
return 0 # Прекращаем игру
moves = [game(first_heap + 1), game(first_heap * 2), game(first_heap * 3)] # Прописываем ходы возможные в партии
petya_win = [i for i in moves if i <= 0]
if petya_win: # Проверяем есть ли выигрыш Пети в данной позиции
return -max(petya_win) + 1
else: # Если в данной позиции выигрыш Вани
return -max(moves)
for i in range(1, 42 + 1):
if game(i) == -1: # Если в данной позиции Ваня гарантированно выигрывает своим первым ходом
print(i)
break # Первое выведенное значение будет минимальным
Решение АР
from functools import lru_cache
def moves(h):
return h + 1, h * 2, h * 3
@lru_cache(None)
def f(h):
if h >= 43 and h <= 72:
return ’END’
if h > 72:
return ’BAD’
if any(f(x) == ’END’ for x in moves(h)):
return ’WIN1’
if all(f(x) == ’WIN1’ for x in moves(h)):
return ’LOSE1’
if all(f(x) == ’WIN1’ or f(x) == ’BAD’ for x in moves(h)):
return ’LOSE1 or BAD’
for i in range(1, 43):
if f(i) == ’LOSE1’ or f(i) == ’LOSE1 or BAD’:
print(i)
break