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

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

19

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

  1. убрать из кучи пять камней;
  2. если количество камней в куче чётно, уменьшить его в два раза;
  3. если количество камней в куче кратно трём, уменьшить его в три раза;
  4. если количество камней в куче нечётно и не кратно трём, добавить один камень.

Например, если в куче \(12\) камней, то за один ход можно получить \(7,\) \(6\) или \(4\) камня, а если в куче \(11\) камней, то за один ход можно получить \(6\) или \(12\) камней. Игра завершается, когда количество камней в куче становится не более \(19.\) Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет \(19\) или меньше камней.

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

20

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

21

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

Решение:

Python


def moves(h):
    m = [h - 5,]
    if h % 2 == 0:
        m += [h // 2]
    if h % 3 == 0:
        m += [h // 3]
    if h % 2 and h % 3:
        m += [h + 1]
    return m

def game_over(pos):
    return pos <= 19

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(20, 1000) if lose1(S)]
z20 = [S for S in range(20, 1000) if win2(S)]
z21 = [S for S in range(20, 1000) if lose2(S)]
print(min(z19))
print(*z20[:2])
print(min(z21))

Ответ:
\(25\)
\(40 \,\, 43\)
\(60\)