Петя и Ваня по очереди ходят в игре с двумя кучами камней. Первым ходит Петя. За один ход игрок может убрать 3 камня из выбранной кучи или разделить число камней в ней на 3, округлив результат вниз.
Игра заканчивается, когда сумма камней в двух кучах становится не более 53. Побеждает тот, кто сделал ход, завершивший игру.
Изначально в первой куче 19 камней, во второй — камней, . Игрок имеет выигрышную стратегию, если может обеспечить победу при любой игре соперника.
Найдите минимальное значение , при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, гарантирующей победу первым ходом.
Решение:
Когда ходит Ваня, достаточно одного подходящего хода (or). Когда ходит Петя, проверяем все ходы (and). Сначала разрешаем победу Вани при x = 3 или x = 5, затем исключаем гарантированную победу при x = 3.
За четыре хода во второй куче останется не меньше (S - 12) // 3 ** 4 камней. Если даже эта нижняя граница больше 53, закончить игру за четыре хода невозможно.
Сдвиг до x = 3 в вызове f оставляет по одному ходу Пете и Ване. Так мы исключаем позиции, где Ваня гарантированно выигрывает своим первым ходом.
def f(k1, k2, x):
if (x == 3 or x == 5) and (k1 + k2 <= 53): return True
if x == 5 and (k1 + k2 > 53): return False
if (k1 + k2 <= 53): return False
if x % 2 == 0:
return (k1 >= 3 and f(k1 - 3, k2, x + 1)) or (k1 > 0 and f(k1 // 3, k2, x + 1)) or (k2 >= 3 and f(k1, k2 - 3, x + 1)) or (k2 > 0 and f(k1, k2 // 3, x + 1))
else:
return (k1 < 3 or f(k1 - 3, k2, x + 1)) and (k1 == 0 or f(k1 // 3, k2, x + 1)) and (k2 < 3 or f(k1, k2 - 3, x + 1)) and (k2 == 0 or f(k1, k2 // 3, x + 1))
for k in range(35, (53 + 1) * 3 ** 4 + 4 * 3):
if f(19, k, 1) and not f(19, k, 3):
print(k)
Ответ — 111.