Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить три камня или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который только что сделал второй игрок. Например, если в начале игры в куче 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)])
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по
очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу два камня, пять камней
или 15 камней. Изменять количество камней в большей куче не разрешается. Игра завершается, когда общее
количество камней в двух кучах становится более 90. Победителем считается игрок, сделавший последний ход, то есть
первым получивший 91 или больше камней в двух кучах. В начальный момент в первой куче было 15 камней, а во
второй – S камней, 
.
Укажите такие значений S, при которых Петя не может выиграть за один ход, но при любом ходе Пети Ваня сможет выиграть своим первым ходом. Числа запишите в порядке возрастания без пробелов и разделителей.
Решение
Максимальный ход, который мы имеем в игре это +15, это значит, что промежуток, в котором игрок выигрывает в один ход располагается от 76 до 91(по сумме количества камней в кучах).
Значит, Ваня выиграет первым ходом, если после хода Пети сумма камней в кучах будет находится в определённом ранее промежутке.
Подходящие нам случаи происходят при 59 и 60 камнях во второй куче. В независимости какой ход сделает Петя, сумма камней в кучах будет находиться в нашем промежутке и в итоге Ваня выиграет своим первым ходом. Ответ:5960.
Решение программой
from functools import lru_cache lru_cache(None) def f(a,b,c = 0):# Параметр ’с’ в этой программе - это счётчик,сделанных ходов в данной партии. # В данной задаче он обязателен,поскольку изначальное кол-во камней может быть слишком мало,а также есть ходы,которые не так сильно увеличивают кол-во камней в куче(+2,+5),как,например ход (+15). # По этой причине у нас может возникнуть ошибка,связанная с превышением глубины рекурсии или же программа будет слишком долго высчитывать значения. if a+b >= 91: return 0 if c > 10: return 1000 if a < b: t = [f(a+2,b,c+1),f(a+5,b,c+1),f(a+15,b,c+1)] else: t = [f(a,b+2,c+1),f(a,b+5,c+1),f(a,b+15,c+1)] n = [i for i in t if i <= 0] if n: return -max(n) + 1 return -max(t) for i in range(1,61): if f(15,i) == -1: print(i)
