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

Задания

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

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

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

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

Решение. Такое значение S  — 24. При S  =  27 Петя своим первым ходом может получить позиции 25, 28 и 72. При позиции 72 Ваня утраивает количество камней в куче в 3 раза и выигрывает своим первым ходом. В позиции 25 Ваня добавляет в кучу четыре камня и получает позицию 29. В позиции 28 Ваня добавляет в кучу один камень и получает позицию 29. Петя своим вторым ходом может получить позиции 30, 33 или 87. Во всех случаях Ваня утраивает количество камней и выигрывает своим вторым ходом.

Ответ: 24.

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

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

def f(x, h):

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

return 1

elif h == 5 and x < 88:

return 0

elif x >= 88 and h < 5:

return 0

else:

if h % 2 == 0:

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

else:

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

def f1(x, h):

if h == 3 and x >= 88:

return 1

elif h == 3 and x < 88:

return 0

elif x >= 88 and h < 3:

return 0

else:

if h % 2 == 0:

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

else:

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

№ п/п	№ задания	Ответ
1	59699	24

Ключ