ЕГЭ–2026, информатика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 20 № 28115 Добавить в вариант

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: добавить в кучу один камень (действие А) или утроить количество камней в куче, а затем убрать из кучи один камень (действие Б). Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 29 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится более 32. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 33 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 32.

Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока  — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

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

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

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

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

Спрятать решение

Решение.

Возможные значения S: 4, 10. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 11 камней (при S = 4 он выполняет действие Б; при S = 10  — добавляет один камень (выполняет действие А)). Тогда после первого хода Вани в куче будет 12 камней или 32 камень. Во всех случаях Петя увеличивает количество камней в куче в 3 раза и выигрывает вторым ходом.

Таким образом, ответ  — 410.

Ответ: 410.

Приведём другое решение на языке Python.

def f(x, h):

if h == 4 and x >= 33:

return 1

elif h == 4 and x < 33:

return 0

elif x >= 33 and h < 4:

return 0

else:

if h % 2 != 0:

return f(x + 1, h + 1) or f(x * 3 - 1, h + 1) # стратегия победителя

else:

return f(x + 1, h + 1) and f(x * 3 - 1, h + 1) # стратегия проигравшего

for x in range(1, 33):

if f(x, 1) == 1:

print(x)

Раздел кодификатора ФИПИ: 1.5.2 Цепочки, деревья, списки, графы, матрицы, псевдослучайные последовательности

Спрятать решение · Помощь

Тип 19 № 28114 Добавить в вариант

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Решение · Помощь

Тип 21 № 28116 Добавить в вариант

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

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

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

Решение.

Минимальное значение S: 9. После первого хода Пети в куче будет 10 или 26 камней. Если в куче станет 26 камней, Ваня увеличит количество камней в куче в 3 раза и выиграет первым ходом. В ситуации, когда в куче 10 камней, Ваня добавляет в кучу 1 камень таким образом, чтобы получилось 11 камней. В этом случае при любой игре Пети Ваня выигрывает своим следующим ходом.

Таким образом, ответ  — 9.

Ответ: 9.

Приведём другое решение на языке Python.

Исключим стратегию Вани, которая позволит ему гарантированно выиграть первым ходом:

def f(x, h):

if (h == 3 or h == 5) and x >= 33:

return 1

elif h == 5 and x < 33:

return 0

elif x >= 33 and h < 5:

return 0

else:

if h % 2 == 0:

return f(x + 1, h + 1) or f(x * 3 - 1, h + 1) # стратегия победителя

else:

return f(x + 1, h + 1) and f(x * 3 - 1, h + 1) # стратегия проигравшего

def f1(x, h):

if h == 3 and x >= 33:

return 1

elif h == 3 and x < 33:

return 0

elif x >= 33 and h < 3:

return 0

else:

if h % 2 == 0:

return f1(x + 1, h + 1) or f1(x * 3 - 1, h + 1) # стратегия победителя

else:

return f1(x + 1, h + 1) and f1(x * 3 - 1, h + 1) # стратегия проигравшего(любой ход)

for x in range(1, 33):

if f(x, 1) == 1:

print(x)

print("====")

for x in range(1, 33):

if f1(x, 1) == 1:

print(x) # Исключим эти значения из списка выше

Решение · Помощь