Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который только что сделал второй игрок.
Например, если в начале игры в куче 
камня, Петя может первым ходом получить кучу из 
или 
камней. Если
Петя получил кучу из 
камней (добавил 
камня), то следующим ходом Ваня может получить 
или 
камней.
Получить 
камней Ваня не может, так как для этого нужно добавить 
камня, а такой ход только что сделал
Петя.
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество
камней в куче становится не менее 
. Победителем считается игрок, сделавший последний ход, то есть первым
получивший кучу, в которой будет 
или больше камней.
В начальный момент в куче было 
камней, 
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите такое значение 
при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может
выиграть своим первым ходом.
Решение руками
Для начала найдём все позиции 
. Это позиции 
Рассмотрим позицию 
Из неё Петя утроением
камней достигнет позиции 
из которой Ваня выиграет добавив в кучу 
камня.
Решение программой
from functools import lru_cache def moves(heap): h, k = heap m = [] if k != 0: m += [(h + 1, 0)] if k != 1: m += [(h + 2, 1)] if k != 2: m += [(h * 3, 2)] return m @lru_cache(None) def game(heap): if heap[0] >= 50: return ’END’ elif any(game(x) == ’END’ for x in moves(heap)): return ’P1’ elif all(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, 50): if game((s, -1)) == ’V1’: print(s)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
