19.06 Условие проигрыша

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(first_heap):  # Функция игры
    if first_heap > 72:  # Если камней в куче стало более 72
        return 1  # Возвращаем 1, означающую победу Вани "первым ходом" из-за плохого хода Пети
    if first_heap >= 43:  # Если камней в куче стало не менее 43
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1), game(first_heap * 2), game(first_heap * 3)]  # Прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win:  # Проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else:  # Если в данной позиции выигрыш Вани
        return -max(moves)


for i in range(1, 42 + 1):
    if game(i) == -1:  # Если в данной позиции Ваня гарантированно выигрывает своим первым ходом
        print(i)
        break  # Первое выведенное значение будет минимальным

Решение АР

from functools import lru_cache

def moves(h):
    return h + 1, h * 2, h * 3

@lru_cache(None)
def f(h):
    if h >= 43 and h <= 72:
        return ’END’
    if h > 72:
        return ’BAD’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if all(f(x) == ’WIN1’ or f(x) == ’BAD’ for x in moves(h)):
        return ’LOSE1 or BAD’

for i in range(1, 43):
    if f(i) == ’LOSE1’ or f(i) == ’LOSE1 or BAD’:
        print(i)
        break