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

Задания

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

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

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

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

Ответ:

Решение. Такие значения S  — 93 и 102.

При значении S  =  93 Петя своим первым ходом может получить позиции 94, 103 и 465. При позиции 465 Ваня увеличивает количество камней в куче в пять раз и выигрывает своим первым ходом. В позиции 94 Ваня добавляет в кучу десять камней и получает позицию 104. В позиции 103 Ваня добавляет в кучу один камень и получает позицию 104. Петя своим вторым ходом может получить позиции 105, 114 или 520. Во всех случаях Ваня увеличивает в пять раз количество камней и выигрывает своим вторым ходом.

При значении S  =  102 Петя своим первым ходом может получить позиции 103, 112 и 510. При позициях 112 и 510 Ваня увеличивает количество камней в куче в пять раз и выигрывает своим первым ходом. В позиции 103 Ваня добавляет в кучу один камень и получает позицию 104. Петя своим вторым ходом может получить позиции 105, 114 или 520. Во всех случаях Ваня увеличивает в пять раз количество камней и выигрывает своим вторым ходом.

Ответ: 93 102.

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

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

def f(x, h):

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

return 1

elif h == 5 and x < 525:

return 0

elif x >= 525 and h < 5:

return 0

else:

if h % 2 == 0:

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

else:

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

def f1(x, h):

if h == 3 and x >= 525:

return 1

elif h == 3 and x < 525:

return 0

elif x >= 525 and h < 3:

return 0

else:

if h % 2 == 0:

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

else:

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

№ п/п	№ задания	Ответ
1	59814	93 102

Ключ