Главная ФИПИ

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

Задание 20. Выигрышная стратегия

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

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

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

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

Серия: 0

О теме

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

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

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

ФИПИ № 08622F ↗Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в два раза. Например, имея кучу из 12 камней, за один ход можно получить кучу из 13, 16 или 24 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 36 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 35. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

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

-       Петя не может выиграть за один ход;

-       Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

 

Показать ответ
Ответ: 13 16
Решение.
  1. Позиция выигрышна за один ход (W1), если одним ходом можно получить 36 или больше камней. Самый сильный ход — удвоить кучу: значит, W1 — это все кучи от 18 до 35 камней, ведь 18·2 = 36 ≥ 36, а 17·2 = 34 < 36. Позиция L1 (проигрыш за один ход) — из неё нельзя выиграть сразу, но любой ход ведёт в W1.
  2. L1-позиции в одной куче: 17. Петя выигрывает вторым ходом (W2), если сразу выиграть нельзя, но есть ход в L1.
  3. S = 13: позиция 13, Петя сразу не выигрывает (максимум 26 < 36); его ход в 17 — позицию, где Петя не выиграл бы за один ход, но любой ход ведёт в W1. Оттуда ходы Вани: 18, 21, 34 — после любого Петя выигрывает вторым ходом.
  4. S = 16: позиция 16, Петя сразу не выигрывает (максимум 32 < 36); его ход в 17 — позицию, где Петя не выиграл бы за один ход, но любой ход ведёт в W1. Оттуда ходы Вани: 18, 21, 34 — после любого Петя выигрывает вторым ходом.
  5. Программа: 
    def f(s, m):
    if s >= 36:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, m - 1) for x in [s + 1, s + 4, s * 2]]
    return any(h) if m % 2 == 1 else all(h)

print([s for s in range(1, 36) if f(s, 3) and not f(s, 1)])
  6. Ответ: 13 16.