19.07 Прочие прототипы
Ошибка.
Попробуйте повторить позже
Два игрока, Рик и Морти, играют в следующую игру. Перед игроками лежит лист бумаги, на котором написано двоичное
число. Игроки ходят по очереди, первый ход делает Рик. За один ход игрок может приписать справа или слева к
имеющемуся на листе числу двоичную запись любого из чисел вида 
, где 
— произвольное натуральное число,
либо приписать справа и слева от имеющегося на листе числа его копию. Например, имея двоичное число 
, за один
ход можно получить путём копирования число 
или путём приписывания двоичной записи числа 
числа
или 
.
Игра завершается в тот момент, когда количество единиц в двоичной записи числа на листе станет больше или равно
. Победителем считается игрок, сделавший последний ход, т. е. первым получивший двоичное число, в записи которого
использовано 
или более единиц.
В начальный момент единиц в числе было 
.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Морти выиграл своим первым ходом после неудачного первого хода Рика. Укажите минимальное
значение 
, когда такая ситуация возможна.
from functools import lru_cache def moves(heap): return heap + 2, heap * 3 @lru_cache(None) def game(heap): if heap >= 42: return ’END’ elif any(game(x) == ’END’ for x in moves(heap)): return ’WIN1’ elif any(game(x) == ’WIN1’ for x in moves(heap)): return ’LOSE1’ for s in range(1, 41): if game(s) == ’LOSE1’: print(s) break
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
