Уменьшение кучи и ходы с условием

Что меняется, когда кучу уменьшают?

Только правила: ходы уменьшают кучу, а выигрывает тот, кто первым опустился до порога. Функция g прежняя. Учебная игра: можно убрать один камень или уменьшить кучу вдвое с округлением вниз; выигрывает тот, у кого после хода в куче не более 10 камней; S ≥ 11.

def moves(s):    return [s - 1, s // 2]  def finished(s):    return s <= 10  print(moves(21), moves(22))

// — деление с округлением вниз: 21 // 2 = 10, поэтому из 21 выигрывают сразу. А из 22 делением получится 11 — игра продолжается.

Где здесь В1, П1, В2 и П2?

Определения те же, только конец игры теперь внизу: ближе к победе — меньше камней, и перебор идёт вверх от порога. В1 — 11–21. П1 — 22: оба хода, в 21 и в 11, ведут в В1. В ловушку 22 ведут 23 (−1), 44 и 45 (44 // 2 = 45 // 2 = 22) — это В2. П2 — 24 и 46.

Программа находит то же:

from functools import cache  def moves(s):    return [s - 1, s // 2]  def finished(s):    return s <= 10  @cachedef g(s):    nxt = moves(s)    if any(finished(q) for q in nxt):        return 1  # В1    r = [g(q) for q in nxt]    if all(x == 1 for x in r):        return -1  # П1    if -1 in r:        return 2  # В2    if all(x > 0 for x in r):        return -2  # П2    return 0  starts = range(11, 60)print([s for s in starts if g(s) == -1])print([s for s in starts if g(s) == 2])print([s for s in starts if g(s) == -2])

Как записать «уменьшить в два раза» в коде?

Так, как сказано в условии: округление вниз, вверх или «только если делится нацело» — это три разных хода.

с округлением вниз

s // 221 // 2 = 10

с округлением вверх

(s + 1) // 2(21 + 1) // 2 = 11

если делится нацело

if s % 2 == 021 на 2 не делится — хода нет

Обычное деление и round не подходят: 21 / 2 даёт дробное 10.5, а round(10.5) — 10, потому что округляет к чётному:

print(21 // 2, (21 + 1) // 2, 21 / 2, round(10.5))

Деление на 3 с округлением вверх — (s + 2) // 3: к числу добавляют делитель без единицы.

В условии «S ≥ 11», а сверху границы нет. До какого S перебирать?

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

Быстрее всего куча убывает от двух делений подряд: из S получается S // 4. Чтобы Ваня дошёл до порога, нужно S // 4 ≤ 10, а это верно только до S = 43: 43 // 4 = 10, но 44 // 4 = 11. Значит, ответ не больше 43, и перебора до 1000 хватит с запасом:

from functools import cache  def moves(s):    return [s - 1, s // 2]  def finished(s):    return s <= 10  @cachedef g(s):    nxt = moves(s)    if any(finished(q) for q in nxt):        return 1  # В1    r = [g(q) for q in nxt]    if all(x == 1 for x in r):        return -1  # П1    if -1 in r:        return 2  # В2    if all(x > 0 for x in r):        return -2  # П2    return 0  def mistake(s):    return any(not finished(q) and g(q) == 1               for q in moves(s))  print(max(s for s in range(11, 1000) if mistake(s)))

Если спрашивают о гарантии — «при любом ходе Пети Ваня выигрывает первым ходом», — граница другая. Ваня должен выиграть даже после самого медленного хода Пети, здесь это −1. Значит, S − 1 должно быть В1, то есть S − 1 ≤ 21 и S ≤ 22. Дальше П1 быть не может.

Как записать ход, который разрешён не всегда?

В moves ход добавляют только после проверки условия. Пусть делить пополам можно только чётную кучу:

from functools import cache  def moves(s):    result = [s - 1]    if s % 2 == 0:        result.append(s // 2)    return result  def finished(s):    return s <= 10  @cachedef g(s):    nxt = moves(s)    if any(finished(q) for q in nxt):        return 1  # В1    r = [g(q) for q in nxt]    if all(x == 1 for x in r):        return -1  # П1    if -1 in r:        return 2  # В2    if all(x > 0 for x in r):        return -2  # П2    return 0  print(moves(13), moves(14))print([s for s in range(11, 30) if g(s) == -1])

Условие меняет все группы. Без него 13 была В1 (13 // 2 = 6), а теперь из 13 один ход — в 12, а это В1 соперника. Так же пишут «если кратно трём», «добавить делитель числа», «добавлять только в меньшую кучу».

Запрещённый результат тоже убирают в moves. «Превышать 21 нельзя» — [q for q in (s + 1, s * 2) if q <= 21], а finished тогда проверяет s == 21.

Что делает g, если из позиции нет ни одного хода?

Возвращает −1, и это обычно ошибка: для пустого списка all даёт True. Пусть к куче можно добавить её делитель d, 1 < d < s, а выигрывает получивший не менее 30 камней. У простого числа таких делителей нет:

from functools import cache  def moves(s):    return [s + d for d in range(2, s) if s % d == 0]  def finished(s):    return s >= 30  @cachedef g(s):    nxt = moves(s)    if any(finished(q) for q in nxt):        return 1  # В1    r = [g(q) for q in nxt]    if all(x == 1 for x in r):        return -1  # П1    if -1 in r:        return 2  # В2    if all(x > 0 for x in r):        return -2  # П2    return 0  print(moves(12), moves(7), g(7))

Из 7 Петя не может сходить вовсе, а программа назвала 7 позицией П1: ни одного хода — значит, «все ходы ведут в В1». all([]) верен, потому что нарушений нет. Что значит позиция без ходов, решает условие. Если она не должна попадать в ответ, добавь в начало g строку if not nxt: return 0 — сразу после nxt = moves(s).

• Уменьшениете же группы; перебор вверх от порога
• Внизs // 2
• Вверх(s + 1) // 2
• Наибольшее Sграница — самый быстрый спуск до порога
• Ход с условиемдобавить в moves после if
• Нет ходовall([]) — True: решить по условию