19.07 Прочие прототипы
Ошибка.
Попробуйте повторить позже
Два игрока, Аня и Амина, играют в следующую игру. Перед игроками лежит лист бумаги, на котором написано два
двоичных числа. Игроки ходят по очереди, первый ход делает Аня. За один ход игрок может приписать справа к любому
имеющемуся на листе числу двоичную запись любого из чисел вида 
, где 
— произвольное натуральное число,
либо приписать слева и справа от имеющихся на листе чисел его копию. Например, имея двоичные числа 
и 
, за
один ход можно получить путём копирования числа 
или 
или путём приписывания двоичной
записи числа 
получить числа 
или 
.
Игра завершается в тот момент, когда суммарное количество единиц в двоичной записи чисел на листе станет больше
или равно 
. Победителем считается игрок, сделавший последний ход, т. е. первым получивший суммарно в записи
чисел 
или более единиц (Например 
и 
— сумма 4).
В начальный момент единиц в первом числе было 
единиц, а во втором 
.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Амина выиграла своим первым ходом после неудачного первого хода Ани. Укажите минимальное
значение 
, когда такая ситуация возможна.
# Т.к. при решении мы оперируем количеством единиц в двоичной записи, то двоичное число 11001 - это # то же самое, что и число 3 в обычной задаче на теорию чисел на кучи # Если к числу слева и справа приписать его же, у нас запись утроится, и количество единиц станет # в 3 раза больше, если к числу приписать число вида 2̂(2n-1), то количество единиц увеличится на 1 # ПРИМЕР - 2̂(2-1) = 2, 2 = 10, если приписать 10 к записи, то получится на 2 единицы больше # Или же 2̂(4-1) = 8, 8 = 1000, аналогичная история, как и для числа 2. # То есть, у таких чисел в записи содержится только 1 единица, т.к. они являются степенями двойки. from functools import lru_cache @lru_cache(None) def f(a, b): if a + b >= 100: return 0 moves = [f(a + 1, b), f(a * 3, b), f(a, b + 1), f(a, b * 3)] anya_win = [i for i in moves if i <= 0] if anya_win: return -max(anya_win) + 1 return -max(moves) for i in range(1, 93): if f(7 + 1, i) == 1 or f(7 * 3, i) == 1 or f(7, i + 1) == 1 or f(7, i * 3) == 1: print(i)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
