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

Задания

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

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

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

Решение. Такое значение S  — 112. При S  =  112 Петя своим первым ходом может получить позиции 113, 117 и 448. При позиции 448 Ваня увеличивает количество камней в куче в 4 раза и выигрывает своим первым ходом. В позиции 113 Ваня добавляет в кучу пять камней и получает позицию 118. В позиции 117 Ваня добавляет в кучу один камень и получает позицию 118. Петя своим вторым ходом может получить позиции 119, 123 или 472. Во всех случаях Ваня увеличивает в четыре раза количество камней и выигрывает своим вторым ходом.

Ответ: 112.

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

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

def f(x, h):

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

return 1

elif h == 5 and x < 473:

return 0

elif x >= 473 and h < 5:

return 0

else:

if h % 2 == 0:

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

else:

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

def f1(x, h):

if h == 3 and x >= 473:

return 1

elif h == 3 and x < 473:

return 0

elif x >= 473 and h < 3:

return 0

else:

if h % 2 == 0:

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

else:

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

№ п/п	№ задания	Ответ
1	59726	112

Ключ