Главная ФИПИ

ФИПИ · ЕГЭ · Информатика · Задание 21

Задание 21. Дерево игры

43 заданий открытого банка ФИПИ: впишите ответ, при затруднении — подсказка; после ответа — разбор по шагам.

0
Решено
0
Правильно
0%
Точность

Задания открытого банка ФИПИ «Задание 21. Дерево игры» (информатика). Ответ вписывается так же, как в бланк ЕГЭ: число, слово или цифры подряд, без пробелов; если в ответе два числа — через пробел, как в таблице ответа (по строкам).

Неофициальная копия. Условия заданий — из открытого банка заданий ФИПИ (fipi.ru); номер у каждого задания открывает его в банке ФИПИ. Ответы, подсказки, разборы и рисунки подготовлены reknow.ru. Нашли ошибку — нажмите «Сообщить об ошибке» у задания.

Серия: 0

О теме

Задание 21 ЕГЭ по информатике. Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию. На странице — 43 задания открытого банка ФИПИ: ответ проверяется сразу, есть подсказка и подробный разбор.

Примеры заданий

Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.

ФИПИ № 021805 ↗Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 65. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах находится 65 или больше камней. В начальный момент в первой куче было шесть камней, во второй куче – S камней; 1 ≤ S ≤ 58. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

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

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

–   у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если найдено несколько значений S, в ответе запишите наименьшее из них.

Показать ответ
Ответ: 18
Решение.
  1. Ходы: добавить 1 в одну из куч или умножить одну из куч на 3; игра заканчивается, когда сумма станет ≥ 65. Обозначим позиции: W1 — выигрыш одним ходом; L1 — все ходы ведут в W1 (соперник выигрывает первым ходом); W2 — есть ход в L1; L2 — все ходы ведут в W1 или W2, и хотя бы один — в W2.
  2. Нужна позиция L2: любой ход Пети ведёт в W1 или W2 (Ваня выигрывает первым или вторым ходом), и хотя бы один ход ведёт в W2 (выигрыш первым ходом не гарантирован).
  3. S = 18: ходы Пети из (6, 18): (7, 18) — W2; (18, 18) — W1; (6, 19) — W2; (6, 54) — W1. Из W1 Ваня выигрывает сразу, из W2 — переводит игру в L1 и выигрывает вторым ходом.
  4. Подходящие S: 18; наименьшее — 18.
  5. Программа: 
    from functools import lru_cache
T = 65
def moves(p):
    a, b = p
    return [(a + 1, b), (a * 3, b), (a, b + 1), (a, b * 3)]

@lru_cache(None)
def status(p):
    nxt = moves(p)
    if any(sum(q) >= T for q in nxt): return 'W1'
    r = [status(q) for q in nxt]
    if all(x == 'W1' for x in r): return 'L1'
    if 'L1' in r: return 'W2'
    if all(x in ('W1', 'W2') for x in r): return 'L2'
    return '-'

print([s for s in range(1, 59) if status((6, s)) == 'L2'])
  6. Ответ: 18.