Два игрока, Аня и Амина, играют в следующую игру. Перед игроками лежит лист бумаги, на котором написано два двоичных числа. Игроки ходят по очереди, первый ход делает Аня. За один ход игрок может приписать справа к любому имеющемуся на листе числу двоичную запись любого из чисел вида 
, где 
— произвольное натуральное число, либо приписать слева и справа от имеющихся на листе чисел его копию. Например, имея двоичные числа 
и 
, за один ход можно получить путём копирования числа 
или 
или путём приписывания двоичной записи числа 
получить числа 
или 
.
Игра завершается в тот момент, когда суммарное количество единиц в двоичной записи чисел на листе станет больше или равно 
. Победителем считается игрок, сделавший последний ход, т. е. первым получивший суммарно в записи чисел 
или более единиц (Например 
и 
— сумма 4).
В начальный момент единиц в первом числе было 
единиц, а во втором 
.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Амина выиграла своим первым ходом после неудачного первого хода Ани. Укажите минимальное значение 
, когда такая ситуация возможна.
Так как нас интересуют только единички, то очевидно, что при копировании числа у нас единичек становится в 3 раза больше. А при приписывании числа вида 
получаем приписывание 1 единички.
from functools import lru_cache
def moves(h):
a, b = h
return (a + 1, b), (a, b + 1), (a * 3, b), (a, b * 3)
@lru_cache(None)
def f(h):
if (sum(h) >= 100):
return ’END’
if any(f(x) == ’END’ for x in moves(h)):
return ’P1’
if any(f(x) == ’P1’ for x in moves(h)):
return ’V1’
for s in range(1, 92):
h = 7, s
if f(h) == ’V1’:
print(s)
break