Задание №4525.
Построение дерева игры по заданному алгоритму. ЕГЭ по информатике
Для игры, описанной в задании 19, найдите
минимальное значение
S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Пояснение:
Решим задание, написав программу на языке программирования Python.
TARGET = 443
moves = lambda s: (s+1, s+3, s*2)
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)) |
Таким образом,
217 — минимальное значение
S, при котором одновременно выполняются два условия.
Показать ответ
217
Источник: ФИПИ. Открытый банк тестовых заданий
Сообщить об ошибке
Тест с похожими заданиями