Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить три камня или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который только что сделал второй игрок. Например, если в начале игры в куче 4 камня, Петя может первым ходом получить кучу из 5, 7 или 12 камней. Если Петя добавил 1 камень и получил кучу из 5 камней, то следующим ходом Ваня может либо добавить 3 камня (и получить 8 камней), либо утроить количество камней в куче (их станет 15). Получить 6 камней Ваня не может, так как для этого нужно добавить 1 камень, а такой ход только что сделал Петя. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается, когда количество камней в куче становится не менее 100. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 100 или больше камней. В начальный момент в куче было S камней, .
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
# s — кол-во камней, # m — кол-во оставшихся доступных ходов # (чётное изначальное m фактически означает требование к победе Вани, # нечётное — к победе Пети, ниже разберём, к чему), # last — какой ход был предыдущим def f(s,m,last = ’’): # Если возникло нужное кол-во камней — выясняем, победил ли наш фаворит # Работает это так: если победа настала после m ходов, # то остаток от деления на 2 будет 0, значит фаворит победил; # Но если победа настала раньше, разбираем следующим путём: глядя на вызываемые функции, видим, что значение m уменьшается на 1. # Чтобы победил Петя, нужно, чтобы прошло нечётное количество ходов, # таким образом, разность нечётных чисел(m и количество случившихся ходов) даёт нам чётный результат. # Чтобы победил Ваня, соответственно, нужно, чтобы прошло чётное количество ходов, # что даёт нам чётный результат при разности m и количества случившихся ходов(то есть здесь оба числа чётные), # отсюда и проверка на чётность. if s >= 100:return m % 2 == 0 # Если m ходов прошло, а победителя нет — завершаем. if m == 0:return 0 # Здесь формируем списки ходов, исходя из последнего хода противника if last == ’’:h = [f(s+1,m-1,’+1’),f(s+3,m-1,’+3’),f(s*3,m-1,’+3’)] if last == ’+1’:h = [f(s+3,m-1,’+3’),f(s*3,m-1,’+3’)] if last == ’+3’:h = [f(s+1,m-1,’+1’),f(s*3,m-1,’*3’)] if last == ’*3’:h = [f(s+1,m-1,’+1’),f(s+3,m-1,’+3’)] # any(h) — для ходов фаворита, где нам важен хотя бы один выигрышный ход, # all(h) — для ходов соперника, где нам важно, чтобы при любом его ходе фаворит имел выигрышную стратегию return any(h) if (m-1) %2 == 0 else all(h) # Перебор количества камней print([s for s in range(1,100) if f(s,2)])
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!