Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в три раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 
. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет 
или больше камней.
В начальный момент в первой куче было 
камня, во второй куче — 
камней, 
. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение 
, при котором это возможно.
Решение руками
Самый мощный ход в партии это 
. Петя совершит данный ход, чтобы «подарить»победу Ване. Рассмотрим значение и стратегию, при которой Ваня побеждает после неудачного хода Пети:
При 
Петя может увеличить кол-во камней во второй куче в 
раза и тогда станет 
, после чего Ваня увеличивает кол-во камней в куче в 
раза и выигрывает с кучами 
, где сумма Решение БУ
from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap): # Функция игры
if first_heap + second_heap >= 45: # Если камней в куче стало больше 44
return 0 # Прекращаем игру
moves = [game(first_heap, second_heap+1), game(first_heap+1, second_heap),
game(first_heap * 3, second_heap),game(first_heap, second_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,41):
# если в данной позиции после неудачного хода Пети возможен выигрыш Вани
if game(4+1,i) == 1 or game(4*3,i) == 1 or game(4,i+1) == 1 or game(4,i*3) == 1:
print(i)
break
Решение АР
from functools import lru_cache
def moves(h):
a, b = h
return (a, b+1), (a, b*3), (a+1, b), (a*3, b)
@lru_cache(None)
def game(h):
if sum(h) >= 45:
return ’END’
elif any(game(x) == ’END’ for x in moves(h)):
return ’WIN1’
elif any(game(x) == ’WIN1’ for x in moves(h)):
return ’LOSE1’
for s in range(1, 41):
if game((4, s)) == ’LOSE1’:
print(s)
break