Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в большую кучу любое количество камней от одного до трёх или удвоить количество камней в меньшей куче. Если кучи содержат равное количество камней, можно добавить в любую из них от одного до трёх камней, удвоение в этой ситуации запрещено.
Игра завершается, когда общее количество камней в кучах становится
Известно, что Петя смог выиграть первым ходом. Какое наименьшее число камней могло быть суммарно в двух кучах?
Приведём решение на языке Python.
def f(x, y, h):
if h == 1 and x + y >= 41:
return 1
if h == 1 and x + y < 41:
return 0
if h < 1 and x + y >= 41:
return 0
else:
if h % 2 == 0:
if x > y:
return f(x + 1, y, h + 1) or f(x + 2, y, h + 1) or f(x + 3, y, h + 1) or f(x, y * 2, h + 1)
elif x < y:
return f(x, y + 1, h + 1) or f(x, y + 2, h + 1) or f(x, y + 3, h + 1) or f(x * 2, y, h + 1)
elif x == y:
return f(x + 1, y, h + 1) or f(x + 2, y, h + 1) or f(x + 3, y, h + 1) or f(x, y + 1, h + 1) or f(x, y + 2, h + 1) or f(x, y + 3, h + 1)
else:
if x > y:
return f(x + 1, y, h + 1) or f(x + 2, y, h + 1) or f(x + 3, y, h + 1) or f(x, y * 2, h + 1)
elif x < y:
return f(x, y + 1, h + 1) or f(x, y + 2, h + 1) or f(x, y + 3, h + 1) or f(x * 2, y, h + 1)
elif x == y:
return f(x + 1, y, h + 1) or f(x + 2, y, h + 1) or f(x + 3, y, h + 1) or f(x, y + 1, h + 1) or f(x, y + 2, h + 1) or f(x, y + 3, h + 1)
a = set()
for x in range(1, 20):
for y in range(1, 20):
if f(x, y, 0) == 1:
a.add(x + y)
print(min(a))
Ответ: 28.
В игре, описанной
Укажите минимальное и максимальное из таких
В ответе запишите сначала минимальное значение, затем максимальное.
Ответ:
В игре, описанной
Найдите такое значение S, при котором у Вани есть стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.