Если при любом количестве камней в куче первый может сделать ход так, чтобы в куче осталось число камней, отличное и от m, и от n, то он победит. Пусть в куче k камней и ход первого. Если , то первый выигрывает одним ходом (вычитая 10, если , или , если ). Пусть . Первый может оставить в куче либо камень, либо . Если бы в одном случае получалось , а в другом – , число равнялось бы 9.

Значит, для единственное возможное n - это 24.

Ходы для каждого из игроков различны, значит стоит рассматривать выигрышные проигрышные позиции для двух игроков. Иначе говоря, считать не стандартные state[x][y], а state[x][y][type]. Анализ позиций приводит к ответу: выигрывает второй. Позиция S = 20, для первого игрока является позицией типа LOSE5

from functools import lru_cache

def h1(n):
    if (n >= 10):
        return n - 1, n - 10
    else:
        return n - 1, n - 1

def h2(n):
    if (n >= 3):
        return n - 2, n - 3
    else:
        return n - 2, n - 2

@lru_cache(None)
def f1(n):
    if (n == 0):
        return ’END’
    if (any(f2(x) == ’END’ for x in h1(n))):
        return ’WIN1’
    if (all(f2(x) == ’WIN1’ for x in h1(n))):
        return ’LOSE1’
    if (any(f2(x) == ’LOSE1’ for x in h1(n))):
        return ’WIN2’
    if (all(f2(x) == ’WIN1’ or f2(x) == ’WIN2’ for x in h1(n))):
        return ’LOSE2’
    if (any(f2(x) == ’LOSE2’ for x in h1(n))):
        return ’WIN3’
    if (all(f2(x) == ’WIN1’ or f2(x) == ’WIN2’ or \
            f2(x) == ’WIN3’ for x in h1(n))):
        return ’LOSE3’
    if (any(f2(x) == ’LOSE3’ for x in h1(n))):
        return ’WIN4’
    if (all(f2(x) == ’WIN1’ or f2(x) == ’WIN2’ \
            or f2(x) == ’WIN3’ or f2(x) == ’WIN4’ for x in h1(n))):
        return ’LOSE4’
    if (any(f2(x) == ’LOSE4’ for x in h1(n))):
        return ’WIN5’
                                                                                                     
                                                                                                     
    if (
            all(f2(x) == ’WIN1’ or f2(x) == ’WIN2’ or f2(x) == ’WIN3’ \
                or f2(x) == ’WIN4’ or f2(x) == ’WIN5’ for x in
                h1(n))):
        return ’LOSE5’
    if (any(f2(x) == ’LOSE5’ for x in h1(n))):
        return ’WIN6’

@lru_cache(None)
def f2(n):
    if (n < 2):
        return ’END’
    if (any(f1(x) == ’END’ for x in h2(n))):
        return ’WIN1’
    if (all(f1(x) == ’WIN1’ for x in h2(n))):
        return ’LOSE1’
    if (any(f1(x) == ’LOSE1’ for x in h2(n))):
        return ’WIN2’
    if (all(f1(x) == ’WIN1’ or f1(x) == ’WIN2’ for x in h2(n))):
        return ’LOSE2’
    if (any(f1(x) == ’LOSE2’ for x in h2(n))):
        return ’WIN3’
    if (all(f1(x) == ’WIN1’ or f1(x) == ’WIN2’ or \
            f1(x) == ’WIN3’ for x in h2(n))):
        return ’LOSE3’
    if (any(f1(x) == ’LOSE3’ for x in h2(n))):
        return ’WIN4’
    if (all(f1(x) == ’WIN1’ or f1(x) == ’WIN2’ or f1(x) == ’WIN3’ or \
            f1(x) == ’WIN4’ for x in h2(n))):
        return ’LOSE4’
    if (any(f1(x) == ’LOSE4’ for x in h2(n))):
        return ’WIN5’
    if (
            all(f1(x) == ’WIN1’ or f1(x) == ’WIN2’ or f1(x) == ’WIN3’ or \
                f1(x) == ’WIN4’ or f1(x) == ’WIN5’ for x in
                h2(n))):
        return ’LOSE5’
    if (any(f1(x) == ’LOSE5’ for x in h2(n))):
        return ’WIN6’
print(f1(20))

 

Ходы симметричны, а значит стратегия дополнения до 11. Первый выигрывает забрав 1 камень.

Решение руками

Рассмотрим Из этой позиции Петя может сходить в или а из этих позиций Ваня сходит либо в , либо в а мы знаем, что это позиции типа .

 

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if heap % 2 == 0:
        m += [heap // 2]
    else:
        if heap > 1:
            m += [heap - 2]
    if heap % 3 == 0:
        m += [heap // 3]
    else:
        if heap > 2:
            m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 2:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1


for s in range(3, 100):
    if game(s) == 4:
        print(s)
        break

Решение руками

Для начала давайте найдём все позиции . Это все Теперь найдём все позиции . Это позиции Рассмотрим позицию Уменьшение на приведёт нас в а это . Теперь Рассмотрим позицию Уменьшение в раза приведёт нас в а это . Пишем их в ответ.

 

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if heap % 2 == 0:
        m += [heap // 2]
    else:
        if heap > 1:
            m += [heap - 2]
    if heap % 3 == 0:
        m += [heap // 3]
    else:
        if heap > 2:
            m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 2:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1


for s in range(3, 100):
    if game(s) == 3:
        print(s)

Решение руками

Рассмотрим Первым ходом Петя делает неудачный ход в после чего Ваня убирает из кучи две трети камней, создавая этим позицию и побеждая.

 

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if heap % 2 == 0:
        m += [heap // 2]
    else:
        if heap > 1:
            m += [heap - 2]
    if heap % 3 == 0:
        m += [heap // 3]
    else:
        if heap > 2:
            m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 2:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1


for s in range(3, 100):
    print(s, game(s), [game(x) for x in moves(s)])

Решение руками

Рассмотрим позицию :

1. Если Петя сходит в , то Ваня ответит ходом, ведущим в , а мы знаем, что Петя проигрывает в этой позиции за один ход;
2. Если Петя сходит в , то Ваня сходит в . Из этой позиции Петя никак не выиграет за один ход, а Ваня победит делением второй кучи;
3. Если Петя сходит в , то Ваня сходит в . Петя никак не выиграет за ход, а Ваня выиграет делением второй кучи;
4. Если Петя сходит в , то Ваня сходит в . Петя не выигрывает за ход, а Ваня побеждает делением второй кучи.

 

Решение Excel

Для решения используем табличку, которую сделали для решения 20 задачи.

Добавляем новый столбец Ваня (второй ход Вани).

Вырежем все значения таблицы (вместе со стартовым, без названий столбцов) и вставим в столбик Петя (первый ход Пети), а после еще три раза вставим табличку в столбик Петя только чуть ниже, чтобы не заходить на значения ранее вставленных табличек.

Перепишем формулы в ячейках, отвечающих за первый ход Пети, так, чтобы не было повторов.

Теперь добавим условное форматирование для первого хода Пети: ячейки сделаем красными (в разделе Главная выберем условное форматирование Правила выделения ячеек Меньше…, в открывшемся окошке записываем и выбираем красный цвет).

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

 

Решение программой

from functools import lru_cache


def moves(heap):
    a, b = heap
    m = []
    if a >= 1:
        m += [(a - 1, b), (a // 2, b)]
    if b >= 1:
        m += [(a, b - 1), (a, b // 2)]
    return m


@lru_cache(None)
def game(heap):
    if sum(heap) <= 12:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(100, 3, -1):
    if game((9, s)) == ’V2’:
        print(s)
        break

Решение руками

Мы знаем, что позиция – это позиция . Значит все позиции, которые ведут в эту, являются . Нам подойдут значения и ). Значит нам подойдёт значение .

 

Решение Excel

Для решения используем табличку, которую сделали для решения 19 задачи.

Добавляем новый столбик — Петя (второй ход Пети).

Вырезаем имеющиеся числовые значения из таблички и вставляем их в ячейку , в неё же записываем =B4-1, а в F4 — =С4

Теперь добавим условное форматирование. Все ячейки, относящиеся к первому столбику Петя, мы окрасим зелёным (в разделе Главная выберем условное форматирование Правила выделения ячеек Меньше…, в открывшемся окошке записываем и выбираем зелёный цвет).

Копируем полученную таблицу в вставляем её три раза. Меняем первые ходы Пети, чтобы не было повторов.

Осталось подставить значения в ячейку Старт, пока хотя бы после одного хода Пети все ячейки после второго не будут зелёными, при этом ячейки Вани не должны быть красными.

 

Решение программой

from functools import lru_cache


def moves(heap):
    a, b = heap
    m = []
    if a >= 1:
        m += [(a - 1, b), (a // 2, b)]
    if b >= 1:
        m += [(a, b - 1), (a, b // 2)]
    return m


@lru_cache(None)
def game(heap):
    if sum(heap) <= 12:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(100, 3, -1):
    if game((9, s)) == ’P2’:
        print(s)
        break

Решение руками

Очевидно, что при Петя выигрывает своим первым ходом (уменьшением кучи, в которой лежит камней, в два раза). Значит при Петя не сможет победить своим первым ходом, зато это сможет сделать Ваня. Ответ .

 

Решение Excel

Создадим табличку, первый столбец которой назовём Старт, четвёртый Петя, а седьмой — Ваня.

В ячейку запишем , а в D4 запишем формулу =СУММ(B4:C4).

Так как Ване нужно победить первым ходом, то выгоднее всего ходить самым агрессивным ходом — делением на два. В ячейку запишем формулу =ЦЕЛОЕ(МАКС(E4:F4)/2), в — =МИН(E4:F4).

В ячейку J4 запишем формулу =СУММ(H4:I4), скопируем и вставим её в следующую клеточку.

В запишем =B4-1, в =C4, а в — =СУММ(E4:F4).

Добавим условное форматирование. Выделим суммы, которые относятся к Пете и затем в разделе Главная выберем условное форматирование Правила выделения ячеек Меньше…, в открывшемся окошке записываем и выбираем красный цвет. Выделим сумму, которая относится к старту, сделаем её зелёной по аналогии с суммой после хода Пети. То же самое сделаем с суммой, которая относится к Ване.

Скопируем полученную таблицу и вставим её три раза, каждый раз чуть ниже предыдущей. Заменим первые ходы Пети, чтобы не было повторов.

В начальную позицию запишем и начнём подставлять значения в ячейку , пока все суммы камней после хода Вани не станут зелёными.

 

Решение программой

from functools import lru_cache


def moves(heap):
    a, b = heap
    m = []
    if a >= 1:
        m += [(a - 1, b), (a // 2, b)]
    if b >= 1:
        m += [(a, b - 1), (a, b // 2)]
    return m


@lru_cache(None)
def game(heap):
    if sum(heap) <= 12:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(100, 3, -1):
    if game((9, s)) == ’V1’:
        print(s)

Решение руками

Мы знаем, что и это позиции . Рассмотрим позицию . Все ходы из неё ведут в , значит это позиция .

 

Решение Excel

Для решения используем табличку, которую сделали для решения 20 задачи.

Добавляем новый столбец — Ваня (второй ход Вани).

Вырежем все значения таблицы (вместе со стартовым, без названий столбцов) и вставим в столбик Петя (первый ход Пети), а после еще раз вставим в столбик Петя только чуть ниже, чтобы не заходить на значения ранее вставленной таблички.

Перепишем формулы в ячейках, отвечающих за первый ход Пети. В первую запишем =B4-1, а во вторую — =B4-3.

Теперь добавим условное форматирование для первого хода Пети: мы их сделаем красными (в разделе Главная выберем условное форматирование Правила выделения ячеек Меньше…, в открывшемся окошке записываем и выбираем красный цвет).

Осталось подставить значения в ячейку Старт. Если после одного хода Пети Ваня может победить вторым (то есть у Пети не будет красных ячеек после второго хода) и/или после другого Ваня может победить первым ходом, то данное значение нам подходит, и его нужно записать в ответ.

 

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if heap >= 1:
        m += [heap - 1]
    if heap >= 3:
        m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 7:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(100, 7, -1):
    if game(s) == ’V2’:
        print(s)
        break

Решение руками

Очевидно, что при Петя выигрывает за один ход. Значит при Ваня проигрывает за один ход — это позиция . При и Петя сходит в и победит за хода. Ответ .

 

Решение Excel

Для решения используем табличку, которую сделали для решения 19 задачи.

Добавляем новый столбец — Петя (второй ход Пети).

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

В пишем формулу =В4-1, а в — =B4-3

Теперь добавим условное форматирование. Все ячейки, относящиеся к первому столбику Петя мы окрасим зелёным (в разделе Главная выберем условное форматирование Правила выделения ячеек Меньше…, в открывшемся окошке записываем и выбираем зелёный цвет).

Осталось подставить значения в ячейку Старт, пока хотя бы после одного хода Пети все ячейки после второго не будут зелёными, при этом ячейки Вани не должны быть красными.

 

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if heap >= 1:
        m += [heap - 1]
    if heap >= 3:
        m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 7:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


count = 0
for s in range(100, 7, -1):
    if game(s) == ’P2’:
        count += 1
print(count)

Решение руками

Очевидно, что Петя должен «сглупить», чтобы изначальная позиция была максимальной.

Значит

 

Решение Excel

Создадим таблицу ходов: первый столбик назовём Старт, второй — Петя (он будет отвечать за позиции, в которые может попасть Петя после своего первого хода), а третий — Ваня (первый ход Вани).

В первую ячейку в столбце Петя записываем формулу =B4-1. Далее из полученного значения рассматриваем ходы Вани и, соответственно, записываем формулу в ячейки столбца Ваня =J4-3 (рассматриваем только один ход, так как Ване выгоднее всего вычесть как можно больше камней, чтобы точно победить, если это возможно в данном случае).

Теперь добавим условное форматирование. Все ячейки, относящиеся к столбику Петя мы окрасим красным (в разделе Главная выберем условное форматирование Правила выделения ячеек Меньше…, в открывшемся окошке записываем и выбираем красный цвет), а те, что относятся к столбцам Старт и Ваня мы сделаем зелёными (делаем аналогично с ходами Пети, только вместо красного цвета выбираем зелёный).

Скопируем табличку с первого хода Пети по второй ход Пети без заголовков и вставим её копию чуть ниже первой, теперь заменим формулу в первом ходе Пети на =B4-3.

Осталось подставить значения в ячейку Старт, пока хотя бы после одного хода Пети ячейка Вани (из Петиной позиции) не станет зелёной. Полученное значение запишем в ответ.

 

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if heap >= 1:
        m += [heap - 1]
    if heap >= 3:
        m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 7:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif any(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(100, 7, -1):
    if game(s) == ’V1’:
        print(s)
        break

from functools import lru_cache

def moves(h):
    a, b = h
    if a > 1 and b > 1:
        return (a - 1, b), (a, b - 1), (a // 2 + (a % 2), b), (a, b // 2 + (b % 2))
    if a > 1:
        return (a - 1, b), (a, b - 1), (a // 2 + (a % 2), b)
    if b > 1:
        return (a - 1, b), (a, b - 1), (a, b // 2 + (b % 2))
    return (a - 1, b), (a, b - 1)

@lru_cache(None)
def f(h):
    if sum(h) <= 32:
        return ’END’
    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 any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’

for i in range(23, 100):
    h = i, 10
    if f(h) == ’LOSE2’:
        print(i)

from functools import lru_cache

def moves(h):
    a, b = h
    if a > 1 and b > 1:
        return (a - 1, b), (a, b - 1), (a // 2 + (a % 2), b), (a, b // 2 + (b % 2))
    if a > 1:
        return (a - 1, b), (a, b - 1), (a // 2 + (a % 2), b)
    if b > 1:
        return (a - 1, b), (a, b - 1), (a, b // 2 + (b % 2))
    return (a - 1, b), (a, b - 1)

@lru_cache(None)
def f(h):
    if sum(h) <= 32:
        return ’END’
    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 any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’

minim = 100000
maxim = 0
for i in range(23, 100):
    h = i, 10
    if f(h) == ’WIN2’:
        minim = min(minim, i)
        maxim = i
print(minim, maxim)

from functools import lru_cache

def moves(h):
    a, b = h
    if a > 1 and b > 1:
        return (a - 1, b), (a, b - 1), (a // 2 + (a % 2), b), (a, b // 2 + (b % 2))
    if a > 1:
        return (a - 1, b), (a, b - 1), (a // 2 + (a % 2), b)
    if b > 1:
        return (a - 1, b), (a, b - 1), (a, b // 2 + (b % 2))
    return (a - 1, b), (a, b - 1)

@lru_cache(None)
def f(h):
    if sum(h) <= 32:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’

for i in range(23, 100):
    h = i, 10
    if f(h) == ’LOSE1’:
        print(i)

from functools import lru_cache

def moves(heap):
    a, b, c = heap
    m = []
    if a > 1:
        m += [(a - 1, b, c), ((a + 1) // 2, b, c)]
    if b > 1:
        m += [(a, b - 1, c), (a, (b + 1) // 2, c)]
    if c > 1:
        m += [(a, b, c - 1), (a, b, (c + 1) // 2)]
    return m

@lru_cache(None)
def game(heap):
    if sum(heap) <= 32:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’

for s in range(12, 100):
    if game((11, 11, s)) == ’LOSE2’:
        print(s)

from functools import lru_cache

def moves(heap):
    a, b, c = heap
    m = []
    if a > 1:
        m += [(a - 1, b, c), ((a + 1) // 2, b, c)]
    if b > 1:
        m += [(a, b - 1, c), (a, (b + 1) // 2, c)]
    if c > 1:
        m += [(a, b, c - 1), (a, b, (c + 1) // 2)]
    return m

@lru_cache(None)
def game(heap):
    if sum(heap) <= 32:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’

count = 0
for s in range(12, 100):
    count += (game((11, 11, s)) == ’WIN2’)
print(count)

from functools import lru_cache

def moves(heap):
    a, b, c = heap
    m = []
    if a > 1:
        m += [(a - 1, b, c), ((a + 1) // 2, b, c)]
    if b > 1:
        m += [(a, b - 1, c), (a, (b + 1) // 2, c)]
    if c > 1:
        m += [(a, b, c - 1), (a, b, (c + 1) // 2)]
    return m

@lru_cache(None)
def game(heap):
    if sum(heap) <= 32:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif any(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’

for s in range(100, 11, -1):
    if game((11, 11, s)) == ’LOSE1’:
        print(s)
        break

from functools import lru_cache
def moves(heap):
    m = []
    if heap > 0:
        m += [heap - 1]
    if heap > 2:
        m += [heap - 3]
    return m
@lru_cache(None)
def game(heap):
    if heap <= 11:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(12, 100):
    print(s, game(s))
# или
from functools import lru_cache
def moves(heap):
    m = []
    if heap > 0:
        m += [heap - 1]
    if heap > 2:
        m += [heap - 3]
    return m
@lru_cache(None)
def game(heap):
    if heap <= 11:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1
                                                                                                     
                                                                                                     
for s in range(1, 100):
    print(s, game(s), [game(x) for x in moves(s)])

from functools import lru_cache
def moves(heap):
    m = []
    if heap > 0:
        m += [heap - 1]
    if heap > 2:
        m += [heap - 3]
    return m
@lru_cache(None)
def game(heap):
    if heap <= 11:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(12, 100):
    print(s, game(s))
# или
from functools import lru_cache
def moves(heap):
    m = []
    if heap > 0:
        m += [heap - 1]
    if heap > 2:
        m += [heap - 3]
    return m
@lru_cache(None)
def game(heap):
    if heap <= 11:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1
                                                                                                     
                                                                                                     
for s in range(1, 100):
    print(s, game(s), [game(x) for x in moves(s)])