Текстовые решения некоторых заданий

1. Демоверсия 2023

1.2. Программное решение

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 129. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 129 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 128.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите минимальное из них.

Разделим вопрос на две части. Во-первых, найдем все значения S при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети.

#Функция принимает 2 значения
#x - кол-во камней на текущей момент
#n - кол-во прошедших ходов
def f3(x,n):
    #Если еще никто не ходил
    if(n==0):
        #Ходит Петя
        #1й вариант добавить 1 камень
        v1=f3(x+1,n+1)
        #2й вариант увеличить количество камней в 2 раза
        v2=f3(x*2,n+1)
        #Если и v1, и v2 приводит Ваню к победе
        #то это удовлетворительный для нас результат
        return v1 and v2
    #Если только что сходил Петя
    elif(n==1):
        #Если он выиграл
        if(x>=129):
            #это неудовлетворительный результат
            return False
        #Если он не выиграл
        else:
            #то у Вани те же 2 варианта как сходить
            #1й вариант добавить 1 камень
            v1=f3(x+1,n+1)
            #2й вариант увеличить количество камней в 2 раза
            v2=f3(x*2,n+1)
            #Если v1 или v2 приводит Ваню к победе
            #то это удовлетворительный для нас результат
            return v1 or v2
    #Если только что сходил Ваня
    elif(n==2):
        #Если он выиграл
        if(x>=129):
            #это удовлетворительный результат
            return True
        #Если он не выиграл
        else:
            #то у Пети те же 2 варианта как сходить
            #1й вариант добавить 1 камень
            v1=f3(x+1,n+1)
            #2й вариант увеличить количество камней в 2 раза
            v2=f3(x*2,n+1)
            #Если и v1, и v2 приводит Ваню к победе
            #то это удовлетворительный для нас результат
            return v1 and v2
    #Если только что сходил Петя второй раз
    elif(n==3):
        #Если он выиграл
        if(x>=129):
            #это неудовлетворительный результат
            return False
        #Если он не выиграл
        else:
            #то у Вани те же 2 варианта как сходить
            #1й вариант добавить 1 камень
            v1=f3(x+1,n+1)
            #2й вариант увеличить количество камней в 2 раза
            v2=f3(x*2,n+1)
            #Если v1 или v2 приводит Ваню к победе
            #то это удовлетворительный для нас результат
            return v1 or v2
    #Если только что сходил Ваня второй раз
    elif(n==4):
        #Если он выиграл
        if(x>=129):
            #это удовлетворительный результат
            return True
        #Если он выиграть не смог, то
        #игра уже слишком затянулась
        else:
            #и это неудовлетворительный результат
            return False

#Переберем начальное кол-во камней
for S in range(1,129):
    #Если при таком кол-ве камней
    #в самом начале игры мы получаем
    #удовлетворительный результат
    if(f3(S,0)):
        #То выводим начальное кол-во
        #камней при котором это произошло
        print(S)

Во-вторых, найдем все значения S при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть первым ходом при любой игре Пети. Это будут значения, которые нам не подходят и которые мы должны выбросить из того, что нам вывела программа выше. 

#Функция принимает 2 значения
#x - кол-во камней на текущей момент
#n - кол-во прошедших ходов
def f4(x,n):
    #Если еще никто не ходил
    if(n==0):
        #Ходит Петя
        #1й вариант добавить 1 камень
        v1=f4(x+1,n+1)
        #2й вариант увеличить количество камней в 2 раза
        v2=f4(x*2,n+1)
        #Если Ваня сможет победить как при v1, так и при v2,
        #то это удовлетворительный для нас результат
        return v1 and v2
    #Если только что сходил Петя
    elif(n==1):
        #Если он выиграл
        if(x>=129):
            #это неудовлетворительный результат
            return False
        #Если он не выиграл
        else:
            #то у Вани те же 2 варианта как сходить
            #1й вариант добавить 1 камень
            v1=f4(x+1,n+1)
            #2й вариант увеличить количество камней в 2 раза
            v2=f4(x*2,n+1)
            #Если v1 или v2 приводит Ваню к победе
            #то это удовлетворительный для нас результат
            return v1 or v2
    #Если только что сходил Ваня
    elif(n==2):
        #Если он выиграл
        if(x>=129):
            #это удовлетворительный результат
            return True
        #Если он выиграть не смог, то
        #игра уже слишком затянулась
        else:
            #и это неудовлетворительный результат
            return False

#Переберем начальное кол-во камней
for S in range(1,129):
    #Если при таком кол-ве камней
    #в самом начале игры мы получаем
    #удовлетворительный результат
    if(f4(S,0)):
        #То выводим начальное кол-во
        #камней при котором это произошло
        print(S)

Первая программа выводит 62 и 64, вторая программа выводит 64. В ответ идет то число, которое было выведено первой программой, но не было выведено второй.

Ответ: 62.