Задание №4591.
Построение дерева игры по заданному алгоритму. ЕГЭ по информатике
Для игры, описанной в задании 19, найдите минимальное значение
S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений
S, в ответе укажите наименьшее из них.
Пояснение:
Решим задание, написав программу на языке программирования Python.
TARGET = 59
def moves(a,b): return [(a+1,b),(a*2,b),(a,b+1),(a,b*2)]
def win(s): return s[0]+s[1] >= TARGET
for S in range(1,54):
init = (5,S)
# У Вани нет стратегии выигрыша первым ходом
if all(not win(m) for m in moves(*init)):
ok = True
# Для любого хода Пети Ваня должен выиграть первым или вторым своим ходом
for m1 in moves(*init):
if not any(
win(r) or all(not win(m2) and any(win(m3) for m3 in moves(*m2)) for m2 in moves(*r))
for r in moves(*m1)
):
ok = False
break
if ok:
print(S)
break |
Таким образом,
23 — минимальное значение
S, при котором одновременно выполняются два условия.
Показать ответ
23
Источник: ФИПИ. Открытый банк тестовых заданий
Сообщить об ошибке
Тест с похожими заданиями