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

Задания

В игре, описанной в задании 19, в начальный момент в первой куче был 31 камень, а во второй  — S камней, 1 ≤ S ≤ 39.

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

Решение. Рассмотрим значение S  =  16. Своим первым ходом Петя может получить позиции (32, 31), (16, 32), (16, 33) и (16, 34). В позиции (32, 31) Ваня выигрывает первым ходом, увеличив количество камней в меньшей куче в два раза. При позиции (16, 32) Ваня делает позицию (32, 32), Петя может получить позиции (32, 33), (32, 34) и (32, 35), Ваня выигрывает, увеличив количество камней в меньшей куче в два раза. При позициях (16, 33) и (16, 34) Ваня делает позицию (16, 36), тогда Петя может получить позиции (32, 36), (16, 37), (16, 38) и (16, 39). В позиции (32, 36) Ваня выигрывает увеличив количество камней в меньшей куче в два раза, в позициях (16, 37), (16, 38) и (16, 39) Ваня добавляет три камня в большую кучу и выигрывает своим вторым ходом.

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

def Win(ma, mi, k):

ma, mi = max(ma, mi), min(ma, mi)

return 0 if ma >= 40 or mi >= 40 else any([Lose(ma+i,mi,k-1) for i in range(1,4)] + [Lose(ma,mi*2,k-1)] if ma!=mi\

else [Lose(ma+i,mi,k-1) for i in range(1,4)])

def Lose(ma, mi, k):

ma, mi = max(ma, mi), min(ma, mi)

return 1 if ma >= 40 or mi >= 40 else 0 if not k else\

all([Win(ma+i,mi,k-1) for i in range(1,4)] + [Win(ma,mi*2,k-1)] if ma!=mi else [Win(ma+i,mi,k-1) for i in range(1,4)])

print('21)', *[s for s in range(1,40) if not Lose(31, s, 2) and Lose(31, s, 4)])

Ответ: 16.

№ п/п	№ задания	Ответ
1	58529	16

Ключ