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

Просмотры: 1109
Изменено: 2 февраля 2025

19

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. Если количество камней в куче делится на целое k (2⩽k⩽9), то игрок может убрать из кучи k камней. Если количество камней в куче не делится ни на одно из указанных чисел, игрок убирает один камень, после чего выполняет ход по описанному выше правилу.

Например, если в куче 12 камней, то за один ход можно убрать 2,3,4 или 6 камней, а если в куче 11 камней, то игрок за один ход сначала убирает один камень (остаётся 10), а затем убирает 2 или 5 камней.

Игра завершается, когда количество камней в куче становится не более 15. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 15 или меньше камней.

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

20

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

21

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

Решение:

Python


def moves(h):
    k = [x for x in range(2, 10) if h % x == 0]
    if k:
        return [h - x for x in k]
    else:
        h -= 1
        k = [x for x in range(2, 10) if h % x == 0]
        return [h - x for x in k]

def game_over(pos):
    return pos < 16

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

def lose1(pos):
    return all(win1(m) for m in moves(pos))

def win2(pos):
    return not win1(pos) and any(lose1(m) for m in moves(pos))

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

z19 = [S for S in range(16, 1000) if lose1(S)]
z20 = [S for S in range(16, 1000) if win2(S)]
z21 = [S for S in range(16, 1000) if lose2(S)]
print(min(z19))
print(*z20[:2])
print(min(z21))

Ответ:
22
2430
26