В игре участвуют Екатерина, Петя и Ваня. Они ходят по кругу в этом порядке. За ход можно добавить один камень или удвоить размер кучи. Игра заканчивается, когда в куче не меньше 30 камней. Побеждает сделавший последний ход. Изначально в куче камней, .
Ваня выиграл своим первым ходом. Найдите наименьшее , при котором это возможно.
Решение:
Аргумент n — номер задания, а x — число оставшихся ходов. После каждого хода уменьшаем x на единицу. Очередь определяется по остатку x % 3 с учётом начального значения x.
В №19 Ваня ходит третьим. Ищем одну партию, в которой он выигрывает этим ходом. Поэтому используем any на всех очередях и засчитываем победу при x == 0.
В №20 начинаем с x = 30. На очереди Пети x % 3 == 2, поэтому проверяем все его ходы через all. Если выигрывает Петя, после его хода остаток равен 1. Союз Екатерины и Вани добивается цели, когда игра заканчивается при x % 3 != 1.
В №21 начинаем с x = 4. Здесь остаток 2 перед ходом соответствует очереди Вани, и проверяем все его ходы через all. Победу Екатерины вторым ходом засчитываем при x == 0.
def F(k, x, n):
if k >= 30:
if n == 20:
return x % 3 != 1
return x == 0
if x == 0:
return 0
hod = [F(k + 1, x - 1, n), F(k * 2, x - 1, n)]
return any(hod) if n == 19 or x % 3 != 2 else all(hod)
print([k for k in range(1, 30) if F(k, 3, 19)][0]) # 4
print([k for k in range(1, 30) if F(k, 30, 20)][0]) # 1
print(len([k for k in range(1, 30) if F(k, 4, 21)])) # 2