Задание 19. Информатика. ЕГЭ. Поляков-7380
- Просмотры: 140
- Изменено: 18 января 2025
19
(Е. Джобс) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу четыре камня или увеличить количество камней в куче в два раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее \(20.\) Если при этом в куче оказалось не более \(26\) камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник (при этом победа учитывается как ход противника). В начальный момент в куче было \(S\) камней, \(1 \leqslant S \leqslant 19.\)
Найдите минимальное значение \(S,\) при котором Петя не может выиграть за один ход, но Ваня может выиграть своим первым ходом после любого хода Пети.
20
Для игры, описанной в задании 19, найдите наименьшее и наибольшее значения \(S,\) когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
21
Для игры, описанной в задании 19, найдите минимальное значение \(S,\) при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение:
Python
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))
Ответ:
\(6\)
\(2 \,\, 7\)
\(1\)