Петя и Ваня ходят по очереди. Начинает Петя. За ход можно убрать 5 камней из первой кучи, убрать 3 из второй, разделить первую кучу на 2 с округлением вниз или разделить вторую на 2 с округлением вверх.
Игра заканчивается, когда в двух кучах суммарно не больше 60 камней. Побеждает сделавший последний ход. В первой куче изначально 130 камней, во второй — , где .
После неудачного первого хода Пети Ваня выиграл своим первым ходом. Найдите наибольшее , при котором это возможно.
Решение:
Первую кучу делим через k1 // 2, вторую — через ceil(k2 / 2). В hod включаем только разрешённые ходы. Достаточно одной подходящей пары ходов Пети и Вани, поэтому используем any(hod) на обеих очередях.
from math import ceil
def F(k1, k2, x):
if k1 + k2 <= 60:
return x % 2 == 0
if x == 0:
return 0
hod = []
if k1 >= 5:
hod.append(F(k1 - 5, k2, x - 1))
if k2 >= 3:
hod.append(F(k1, k2 - 3, x - 1))
if k1 > 0:
hod.append(F(k1 // 2, k2, x - 1))
if k2 > 1:
hod.append(F(k1, ceil(k2 / 2), x - 1))
return any(hod)
values = [k for k in range(5, 151)
if F(130, k, 2)]
print(values[-1])
Ответ — 28.
Ответ:
28