Петя и Ваня по очереди ходят в игре с двумя кучами. Первым ходит Петя. За ход можно выбрать одно действие:
- убрать 3 камня из первой кучи и 4 из второй;
- убрать 8 камней из первой кучи и разделить число камней во второй на 2 с округлением вниз;
- разделить число камней в первой куче на 2 с округлением вверх и убрать 10 камней из второй.
Побеждает тот, после чьего хода суммарное число камней в кучах не превышает 200. В первой куче изначально 110 камней, во второй — , где .
Найдите минимальное , при котором Петя не может выиграть за один ход, а Ваня может выиграть своим первым ходом после любого хода Пети.
Решение:
Каждый из трёх ходов меняет обе кучи. Вниз округляем через k2 // 2, вверх — через ceil(k1 / 2). Запускаем F(110, k, 2): после любого хода Пети у Вани должен быть выигрышный ответ.
from math import ceil
def F(k1, k2, x):
if k1 + k2 <= 200:
return x % 2 == 0
if x == 0:
return 0
hod = []
if k1 >= 3 and k2 >= 4:
hod.append(F(k1 - 3, k2 - 4, x - 1))
if k1 >= 8 and k2 >= 2:
hod.append(F(k1 - 8, k2 // 2, x - 1))
if k1 >= 2 and k2 >= 10:
hod.append(F(ceil(k1 / 2), k2 - 10, x - 1))
return any(hod) if x % 2 != 0 else all(hod)
values = [k for k in range(100, 1000)
if F(110, k, 2)]
print(values[0])
Ответ — 198.
Ответ:
198