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 ’P1’ elif any(game(x) == ’P1’ for x in moves(heap)): return ’V1’ elif any(game(x) == ’V1’ for x in moves(heap)): return ’P2’ elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)): return ’V2’ for s in range(1, 41): if game(s) == ’V1’: print(s) break
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
