Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат три кучи камней. Игроки ходят
по очереди, первый ход делает Петя. За один ход игрок может убрать из одной из куч один камень или
уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на 
камень
больше, чем убирается). При любом из ходов кол-во камней в одной из куч должно измениться. Например,
пусть в первой куче будет 
камней, во второй куче 
камней, а в третьей 
камней; такую позицию мы
будем обозначать 
За один ход из позиции 
можно получить любую из четырёх позиций:
Игра завершается в тот момент, когда суммарное количество камней в
кучах становится не более 
Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет
или менее камней. В начальный момент в первой куче было 
камня, во второй куче было 
камня, в третьей куче
камней, 
.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите максимальное значение
когда такая ситуация возможна.
Решение руками
Наиболее неудачным для Пети ходом будет уменьшение наибольшей кучи в 
раза. Будем рассматривать этот случай.
Тогда после этого Ваня уменьшает эту же кучу еще в 
раза и выигрывает.
Решение программой
from functools import lru_cache def moves(heap): a, b, c = heap m = [] if a >= 1: m += [(a - 1, b, c)] if a > 1: m += [((a + 1) // 2, b, c)] if b >= 1: m += [(a, b - 1, c)] if b > 1: m += [(a, (b + 1) // 2, c)] if c >= 1: m += [(a, b, c - 1)] if c > 1: m += [(a, b, (c + 1) // 2)] return m @lru_cache(None) def game(heap): if sum(heap) <= 16: 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(100, 9, -1): if game((3, 4, s)) == ’V1’: print(s) break
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
