Задание №20 ЕГЭ Информатика с ответом и решением
Ответ: 611
Условие
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень либо увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 26.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 26 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 25.
Будем говорить, что игрок имеет выигрышную стратегию, если он может
выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, то есть не являющиеся выигрышными независимо от игры противника.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
Подсказки — как подойти к решению
- Порог победы — двадцать шесть камней. Пометь позиции, из которых игрок выигрывает одним ходом, и позиции, из которых оба его хода (добавить камень и удвоить кучу) ведут только к выигрышу соперника: это и есть проигрышные позиции.
- Учти, что у Вани всего два варианта ответа: добавить камень или удвоить кучу. Если оба варианта оставляют Пете выигрышный ход, Петя победит вторым ходом — найди такие S и выпиши их по возрастанию без разделителей.
Решение
Возможные значения S: 6 и 11. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 12 камней: в первом случае — удвоением, во втором — добавлением одного камня. Тогда после первого хода Вани в куче будет 13 камней или 24 камня. Во всех случаях Петя увеличивает количество камней в куче в 2 раза и выигрывает вторым ходом.
Таким образом, ответ — 611.
Ответ: 611.
Приведём другое решение на языке Python.
def f(x, h):
if h == 4 and x >= 26:
return 1
elif h == 4 and x < 26:
return 0
elif x >= 26 and h < 4:
return 0
else:
if h % 2 != 0:
return f(x + 1, h + 1) or f(x * 2, h + 1) # стратегия победителя
else:
return f(x + 1, h + 1) and f(x * 2, h + 1) # стратегия проигравшего
for x in range(1, 26):
if f(x, 1) == 1:
print(x)
Типичные ошибки
- Одно из значений найдено неверно: возможно, включена куча, из которой Петя побеждает сразу, или пропущен вариант, где Ваня отвечает удвоением и спасается.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №20 по информатике