Для игры, описанной в задании #58099, найдите минимальные два таких значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значение запишите в порядке возрастания через пробел.
Решение руками
Исходя из прошлого задания, мы знаем, что областью проигрыша для второй кучи при 
камнях в первой куче является промежуток от 
до 
. Область проигрыша – это такая область, в которой игрок, попавший в этот промежуток, гарантированно проигрывает в партии.
Левую границу области проигрыша можно сдвигать, изменяя количество в первой куче. Рассмотрим на примере партии, где изначальное количество камней в кучах равно 
и 
. Петя первым ходом сделает 
для первой кучи и тогда область проигрыша для второй кучи будет начинаться с 25-ти камней, а не с 31 как было ранее.
В независимости какой ход сделает Ваня, Петя своим вторым ходом выиграет.
Рассмотрим также пример с позицией, где изначальное количество камней равно 
и 
. Петя сделает ход 
для первой кучи, ход 
для второй кучи он не может избрать, так как в случае данного хода Ваня выиграет своим первым ходом. В данный момент, в позиции 
и 
в кучах, область проигрыша для второй кучи не изменилась.
У Вани есть два варианта: 1) увеличить вторую кучу и попасть в область проигрыша. 2)увеличить первую кучу и сдвинуть левую границу области проигрыша, тем самым попав в неё. В независимости какой вариант выберет Ваня, Петя выиграет вторым ходом. Ответ:
.
Программное решение
from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap): # Функция игры.
if first_heap + second_heap >= 74: # Если сумма камней в кучах стала больше 73
return 0 # Прекращаем игру
moves = [game(first_heap, second_heap+1), game(first_heap+1, second_heap),
game(first_heap * 2, second_heap),game(first_heap, second_heap * 2)] # Генерация всех возможных ходов
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,62):
# если в данной позиции возможен выигрыш Пети вторым ходом
if game(12,i) == 2:
print(i)