Задача #3396

Задания 19–21

Уровень ЕГЭ

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

(О. Лысенков) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один свой ход Петя может добавить в кучу 3 камня или увеличить количество камней в куче в три раза. Ваня за один свой ход может добавить в кучу 5 камней или увеличить количество камней в куче в три раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы. Игра завершается в тот момент, когда количество камней в куче становится не менее 231. Победителем считается игрок, сделавший последний ход, т.е. первым получивший в куче 231 камень или больше. В начальный момент в куче было S камней, 10≤S≤120.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

Для игры, описанной в задании 19, найдите максимальное значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Ответ

68

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

def f(a,m,step):
    if a >= 231: return m % 2 == 0
    if m == 0: return 0
    if step == 'P':
        h = [f(a + 3,m - 1,'V'), f(a * 3,m - 1, 'V')]
    else:
        h = [f(a + 5,m - 1,'P'), f(a * 3,m - 1, 'P')]
    return any(h) if m % 2 else all(h)

print('19)',min(i for i in range(10,121) if f(i,2,'P')))
print('20)',*[i for i in range(10,121) if f(i,3,'P') and (not(f(i,1,'P')))][:2])
print('21)',max(i for i in range(10,121 ) if f(i,4,'P') and (not(f(i,2,'P')))))

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

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