19.07 Прочие прототипы
Ошибка.
Попробуйте повторить позже
Два игрока, Аня и Амина, играют в следующую игру. Перед игроками лежит лист бумаги, на котором написано два
двоичных числа. Игроки ходят по очереди, первый ход делает Аня. За один ход игрок может приписать справа к любому
имеющемуся на листе числу двоичную запись любого из чисел вида 
, где 
— произвольное натуральное число,
либо приписать слева и справа от имеющихся на листе чисел его копию. Например, имея двоичные числа 
и 
, за
один ход можно получить путём копирования числа 
или 
или путём приписывания двоичной
записи числа 
получить числа 
или 
.
Игра завершается в тот момент, когда суммарное количество единиц в двоичной записи чисел на листе станет больше
или равно 
. Победителем считается игрок, сделавший последний ход, т. е. первым получивший суммарно в записи
чисел 
или более единиц (Например 
и 
— сумма 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
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
