РЕШУ ЕГЭ — информатика

Задания

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

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

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

Решение. Такое значение S  — 23. При S  =  23 Петя своим первым ходом может получить позиции 25, 26 и 69. При позиции 69 Ваня утраивает количество камней в куче в 3 раза и выигрывает своим первым ходом. В позиции 25 Ваня добавляет в кучу три камня и получает позицию 28, в позиции 26 Ваня добавляет в кучу два камня и получает позицию 28. Петя своим вторым ходом может получить позиции 30, 31 или 84. Во всех случаях Ваня утраивает количество камней и выигрывает своим вторым ходом.

Ответ: 23.

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

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

def f(x, h):

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

return 1

elif h == 5 and x < 89:

return 0

elif x >= 89 and h < 5:

return 0

else:

if h % 2 == 0:

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

else:

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

def f1(x, h):

if h == 3 and x >= 89:

return 1

elif h == 3 and x < 89:

return 0

elif x >= 89 and h < 3:

return 0

else:

if h % 2 == 0:

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

else:

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

№ п/п	№ задания	Ответ
1	59767	23

Ключ