Задание 19. Информатика. ЕГЭ. Поляков-7380

19

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

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

20

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

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

Найденные значения запишите в ответе в порядке возрастания.

21

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

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

def moves(pos):
    d, f = pos
    if d > 26:
        return (d, True),
    return (d + 4, f), (2 * d, f)

def game_over(pos):
    return pos[1] or 20 <= pos[0] <= 26

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