Код работает неправильно (задача 21)

Question

Проблема: выводит 176 вместо 180 (хотя 180 тоже можно заметить при полном выводе).

Вот условия (21 задача ЕГЭ):

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

убрать из кучи два камня,

уменьшить количество камней в куче в два раза (количество камней, полученное при делении, округляется до меньшего).

У каждого игрока есть неограниченное количество камней, чтобы делать ходы. Игра завершается в тот момент, когда количество камней в куче становится не более 87. Победителем считается игрок, сделавший последний ход, т.е. первым получивший в куче 87 камней или меньше. В начальный момент в куче было S камней, S > 88. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Задание:

Найдите минимальное значение S, при котором одновременно выполняются два условия:

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

у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Код:

def F(x, h):
    if (h == 3 or h == 5) and x <= 87:
        return 1
    if h < 5 and x <= 87:
        return 0
    if h == 5 and x > 87:
        return 0
    else:
        if h % 2 == 0:
            return F(x - 2, h + 1) or F(x//2, h + 1)
        else:
            return F(x - 2, h + 1) and F(x//2, h + 1)
def F1(x, h):
    if h == 3 and x <= 87:
        return 1
    if h < 3 and x <= 87:
        return 0
    if h == 3 and x > 87:
        return 0
    else:
        if h % 2 == 0:
            return F1(x - 2, h + 1) or F1(x//2, h + 1)
        else:
            return F1(x - 2, h + 1) and F1(x//2, h + 1)
m = []
for x in range(88,500):
    if F(x, 1) == 1:
        m.append(x)
for x in range(88,500):
    if F1(x, 1) == 1:
        m.append(x)
print(min(m))

Answer 1

Список m заполняется в двух циклах. Получается мешанина. Вот так будет работать:

m = []
for x in range(88,500):
    if F(x, 1) == 1 and F1(x, 1) == 0:
        m.append(x)
print(min(m))

Другое дело что много дублирования кода. Можно проще:

def moves(n):
    return n - 2, n // 2


# есть ли у Вовы гарантированная победа за k или меньше ходов?
def win(n, k):
    # ситуация перед очередным полуходом Пети
    if n <= 87:
        # победная позиция, Вова победил (мы же перед ходом Пети!)
        return True
    if k == 0:
        # ходы кончились, а Вова ещё не победил
        return False
    for n1 in moves(n):
        # n1 - позиция после полухода Пети
        if n1 <= 87:
            # победа за Петей, то есть Вова выиграть не может
            return False
        if any(win(n2, k - 1) for n2 in moves(n1)):
            # если у Вовы есть хотя бы один выигрышный полуход,
            # продолжаем поиск
            pass
        else:
            # если выигрышного полухода нет, Вова не выигрывает
            return False
    # на любой полуход Пети у Вовы нашёлся какой-то выигрышный ответ. Победа!
    return True


for n in range(88, 1000000):
    # нет гарантированной победы за одну пару полуходов
    # и есть гарантированная победа за две пары полуходов
    if not win(n, 1) and win(n, 2):
        print(n)
        break

Код кажется большим, но это нет так:

def moves(n):
    return n - 2, n // 2


# есть ли у Вовы гарантированная победа за k или меньше ходов?
def win(n, k):
    return n <= 87 or k > 0 and all(
        n1 > 87 and any(win(n2, k - 1) for n2 in moves(n1))
        for n1 in moves(n)
    )


n = 88
while True:
    if not win(n, 1) and win(n, 2):
        break
    n += 1
print(n)

БЛОГ НА HUSL

Код работает неправильно (задача 21)

Ответы (1 шт):