Задания 19-21. Информатика. ЕГЭ. Шастин. 18.12.2024

19

(Д. Бахтиев) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит одна куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня, увеличить количество камней в куче в три раза или добавить в кучу возведённое в квадрат количество камней в ней. Например, пусть в куче \(10\) камней, тогда игрок после своего хода может получить кучу из \(13\) камней, \(30\) камней или \(110\) камней. Игра завершается в тот момент, когда количество камней в куче становится более \(665.\) Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет \(666\) или больше камней. В начальный момент в куче было \(S\) камней, \(S < 666.\)

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

20

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

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

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

21

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

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

def moves(h):
    return h + 3, 3 * h, h + h**2

def game_over(pos):
    return pos > 665

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 lose1_bad(pos):
    return any(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, 666) if lose1_bad(S)]
z20 = [S for S in range(1, 666) if win2(S)]
z21 = [S for S in range(1, 666) if lose2(S)]
print(min(z19))
print(min(z20), max(z20))
print(max(z21))