Задача #3361

Задания 19–21

Уровень ЕГЭ

Общее условие для 19–21

(О. Лысенков) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
- убрать из первой кучи 3 камня и из второй кучи 4 камня;
- убрать из первой кучи 8 камней и уменьшить количество камней во второй куче в 2 раза(количество камней в куче округляется до меньшего);
- уменьшить количество камней в первой куче в 2 раза(количество камней в куче округляется до большего) и убрать из второй кучи 10 камней.
Игра завершается, когда суммарное количество камней в куче становится не более 200. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 200 или менее камней. В начальный момент в первой куче было сто десять камней, а во второй куче S камней, S ≥ 100.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Вопрос для задания 21

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

– Ваня не может выиграть за один ход;
– Ваня может выиграть своим вторым ходом независимо от того, как будет ходить Петя.

Задание 19 Задание 20
Ответ
Войдите, чтобы история ответов и статистика сохранялись.
Решение Нажми, чтобы открыть

Ответ

218

Общий разбор связки

def f(a,b,m):
    if a + b <= 200: return m % 2 == 0
    if m == 0: return 0
    h = [f(a - 3,b - 4,m - 1), f(a - 8,b // 2,m - 1),f(a // 2 + a % 2,b - 10,m - 1)]
    return any(h) if m % 2 else all(h)


print('19)', min([i for i in range(100,1000) if f(110,i,2)]))
print('20)', *[i for i in range(100,1000) if f(110,i,3) and (not f(110,i,1))][:2])
print('21)', min([i for i in range(100,1000) if f(110,i,4) and (not f(110,i,2))]))

Решение для задания 21

Быстрый переход
Перейти к задаче