19.04 Уменьшение количества камней

Решение 1

Подпишем ячейки: — , — . Поместим в ячейке число , а наше значение . В ячейке запишем формулу — там будет сумма камней во время старта

В ячейках запишем все возможные пары куч, которые можно получить: в поместим , в — , в поместим (ЦЕЛОЕ возвращает как раз нужный нам результат деления), в — , в поместим , в — , в поместим , в — . В ячейках столбца будем вести сумму куч (в поместим и растянем эту формулу на все пары куч).

В ячейке запишем формулу . Так мы получим сумму куч после самого аргессивного хода Вжика.

Условно окрасим в зеленый цвет ячейку , если значение в ней меньше 35.

Постепенно перебирая значения ячейки от 50 (например) вниз, заметим, что первый раз все ячейки результата выделяются зеленым при . Значит, это максимальное значение, при котором выполняется условие.

Решение 2

from functools import cache
def moves(h):
    a, b = h
    mesi = []
    if a >= 1:
        mesi.append((a // 2, b))
        mesi.append((a - 1, b))
    if b >= 1:
        mesi.append((a, b // 2))
        mesi.append((a, b - 1))
    return mesi

@cache
def game(h):
    if sum(h) <= 34:
        return ’end’
    if any(game(x) == ’end’ for x in moves(h)):
        return ’win1’
    if all(game(x) == ’win1’ for x in moves(h)):
        return ’lose1’

for i in range(100, 11, -1):
    h = i, 22
    print(i, game(h))