Задания 19-21. Информатика. ЕГЭ. Статград. Профиль. 12.05.2025-1

19

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. Если количество камней в куче делится на целое \(k\) \((0 < k < 31),\) то игрок может убрать из кучи \(k\) камней. Например, если в куче \(36\) камней, то за один ход можно убрать \(1, \, 2, \, 3, \, 4, \, 6, \, 12\) или \(18\) камней. Игра завершается, когда количество камней в куче становится не более \(31.\) Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет \(31\) или меньше камней.

В начале игры в куче было S камней, \(S > 31.\) Укажите максимальное значение \(S,\) при котором Петя не может выиграть первым ходом, но при любом первом ходе Пети Ваня может выиграть своим первым ходом.

20

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

21

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

def divisors(n):
    return [x for x in range(1, 31) if n % x == 0]

def moves(h):
    return [h - x for x in divisors(h)]

def game_over(h):
    return h <= 31

def win1(h):
    return not game_over(h) and any(game_over(m) for m in moves(h))

def lose1(h):
    return not win1(h) and all(win1(m) for m in moves(h))

def win2(h):
    return any(lose1(m) for m in moves(h))

def lose2(h):
    return all(win1(m) or win2(m) for m in moves(h)) \
            and any(win2(m) for m in moves(h))

z19 = [S for S in range(32, 200) if lose1(S)]
z20 = [S for S in range(32, 200) if win2(S)]
z21 = [S for S in range(32, 200) if lose2(S)]
print(max(z19))
print(min(z20), max(z20))
print(max(z21))