Задание №6096.
Построение дерева игры по заданному алгоритму. ЕГЭ по информатике
Для игры, описанной в задании 19, найдите
минимальное значение
S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений
S, в ответе запишите наименьшее из них.
Пояснение:
Решим задание, написав программу на языке программирования Python. Перебираем все
S и проверяем: при любом первом ходе Пети Ваня может либо выиграть сразу, либо выбрать такой ход, что на следующем своём ходе выиграет независимо от ответов Пети. Это даёт стратегию Вани «выиграть первым или вторым ходом». Дополнительно накладывается ограничение: у Вани нет гарантии выиграть всегда первым ходом.
TARGET = 67
moves = lambda s: (s+1, s+4, s*3)
def can_win_immediately(s):
return any(m>=TARGET for m in moves(s))
ans = []
for S in range(1, TARGET):
# для любого хода Пети S1 существует ход Вани v такой, что либо v>=TARGET, либо
# после v для всех ходов Пети p2 существует ход Вани, делающий >=TARGET
good = True
for S1 in moves(S):
if S1>=TARGET:
good = False; break
found = False
for v in moves(S1):
if v>=TARGET:
found = True; break
# проверить: для всех ходов Пети после v у Вани есть ход, дающий >=TARGET
ok2 = True
for p2 in moves(v):
if p2>=TARGET or not any(m>=TARGET for m in moves(p2)):
ok2 = False; break
if ok2:
found = True; break
if not found:
good = False; break
if not good: continue
# и при этом у Вани нет гарантии выиграть уже своим первым ходом:
# существует ход Пети S1, для которого все ходы Вани v < TARGET
if any(all(v < TARGET for v in moves(S1)) for S1 in moves(S)):
ans.append(S)
print(min(ans)) |
Таким образом,
17 — минимальное значение
S, при котором одновременно выполняются два условия.
Показать ответ
17
Источник: Открытый вариант — 2025
Сообщить об ошибке
Тест с похожими заданиями