Для игры, описанной в задании с ID #56420, найдите минимальное из таких значений S, при которых у Вани есть стратегия, позволяющая ему выиграть первым, вторым или третьим ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым или вторым ходом.
Решение
Если после третьего хода Пети сумма камней будет находиться в области проигрыша, то Ваня выиграет третьим ходом. Из прошлых заданий, мы знаем область проигрыша, а также при каких значениях Петя выигрывает своим вторым ходом.
Сразу же определить при каких значениях Ваня выиграет третьим ходом невозможно, для начала нужно вычислить при каком количестве камней во второй куче выигрывает Ваня вторым ходом и Петя третьим ходом. Нам известно, что при такой сумме камней:59,60,69,70,72 и 73 Петя выигрывает своим вторым ходом.
Если после всевозможных первых ходов Пети значение суммы камней будет равным одному из значений, написанных в предыдущем предложении, то при этом исходном значении камней во второй куче будет победа Вани вторым ходом.
Например, при исходном значении суммы камней равной 71, Петя, сделав всевозможные первые ходы получит такие значения суммы камней: 73(одно из значений, описанных ранее),76(область проигрыша),86(область проигрыша). То есть при такой изначальной сумме Ваня победит, первым или вторым ходом зависит от того, будет ли Петя делать неудачные ходы в партии, поскольку в данной задаче Петя делает наилучшие ходы, то при 56-ти камнях во второй куче Ваня выиграет вторым ходом.
Ещё один пример, при исходном значении суммы камней равной 67, Петя, сделав всевозможные первые ходы получит такие значения суммы камней: 69(это одно из значений, описанных ранее),72(одно из значений, описанных ранее),82(область проигрыша).
Получается, что при 52-ух камнях во второй куче Ваня побеждает вторым ходом. В итоге, Ваня выигрывает вторым ходом при таких значениях во второй куче: 52,53,56. Значения суммы камней будет таковым: 67,68,71.
Если после любого первого хода Пети значение суммы камней будет равным одному из значений, в которых Ваня побеждает вторым ходом, то при этом исходном значении камней во второй куче будет победа Пети третьим ходом.
Например, при исходном значении суммы камней равной 52, у Пети есть ход, после которого значение суммы камней будет равным одному из значений суммы камней, описанных в предыдущем предложении.
Значит, при 37-ми камнях во второй куче Петя выиграет третьим ходом. В итоге, Петя выигрывает третьим ходом при таких значениях во второй куче:37,38,41,47,48,50,51. Значения суммы камней будет таковым: 52,53,56,62,63,65,66.
Если после всевозможных первых ходов Пети значение суммы камней будет равным одному из значений, при которым Петя выигрывает третьим ходом, то при этом исходном значении камней во второй куче будет победа Вани третьим ходом.
Например, минимальное значение камней во второй куче, при котором Ваня побеждает третьим ходом, равняется 36. Исходное значение суммы камней равно 51, Петя, сделав всевозможные первые ходы получит такие значения суммы камней:53(одно из значений, в которых Петя побеждает третьим ходом),56(одно из значений, в которых Петя побеждает третьим ходом),66(одно из значений, в которых Петя побеждает третьим ходом). Ответ: 36
Решение программой
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 > 7:
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) == -3:
print(i)