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

Варианты заданий

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в большую кучу любое количество камней от одного до трёх или удвоить количество камней в меньшей куче. Если кучи содержат равное количество камней, можно добавить в любую из них от одного до трёх камней, удвоение в этой ситуации запрещено.

Игра завершается, когда общее количество камней в кучах становится более 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший 41 или больше камней в двух кучах.

В начальный момент в первой куче было 5 камней, а во второй  — S камней, 1 ≤ S ≤ 35.

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

В ответе запишите сначала минимальное значение, затем максимальное.

Ответ:

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

def f(x, y, h):

if h == 3 and x + y >= 41:

return 1

if h == 3 and x + y < 41:

return 0

if h < 3 and x + y >= 41:

return 0

else:

if h % 2 == 0:

if x > y:

return f(x + 1, y, h + 1) or f(x + 2, y, h + 1) or f(x + 3, y, h + 1) or f(x, y * 2, h + 1)

elif x < y:

return f(x, y + 1, h + 1) or f(x, y + 2, h + 1) or f(x, y + 3, h + 1) or f(x * 2, y, h + 1)

elif x == y:

return f(x + 1, y, h + 1) or f(x + 2, y, h + 1) or f(x + 3, y, h + 1) or f(x, y + 1, h + 1) or f(x, y + 2, h + 1) or f(x, y + 3, h + 1)

else:

if x > y:

return f(x + 1, y, h + 1) and f(x + 2, y, h + 1) and f(x + 3, y, h + 1) and f(x, y * 2, h + 1)

elif x < y:

return f(x, y + 1, h + 1) and f(x, y + 2, h + 1) and f(x, y + 3, h + 1) and f(x * 2, y, h + 1)

elif x == y:

return f(x + 1, y, h + 1) and f(x + 2, y, h + 1) and f(x + 3, y, h + 1) and f(x, y + 1, h + 1) and f(x, y + 2, h + 1) and f(x, y + 3, h + 1)

a = set()

for x in range(1, 35):

if f(5, x, 0) == 1:

a.add(x)

print(min(a), max(a))

Ответ: 20  29.

Приведём решение Маргариты Фалько на языке Python.

def g(s1, s2, p, end):

if s1+s2 > 40: return p in end

if p > max(end): return False

moves = []

if s1 > s2:

moves = [g(s1+i, s2, p+1, end) for i in range(1,4)] + [g(s1, s2*2, p+1, end)]

if s1 < s2:

moves = [g(s1, s2+i, p+1, end) for i in range(1,4)] + [g(s1*2, s2, p+1, end)]

if s1 == s2:

moves = [g(s1, s2+i, p+1, end) for i in range(1,4)] + [g(s1+i, s2, p+1, end) for i in range(1,4)]

return any(moves) if ((p+1) % 2) == (end[0] % 2) else all(moves)

print('Задание 19:', min([s1+s2 for s1 in range(1, 100) for s2 in range(1, 100) if g(s1, s2, 0, [1])]))

print('Задание 20:', [s2 for s2 in range(1, 36) if g(5, s2, 0, [3])])

print('Задание 21:', [s2 for s2 in range(1, 24) if g(17, s2, 0, [2, 4]) and not g(17, s2, 0, [2])])

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

Ответ:

№ п/п	№ задания	Ответ
1	55607	20 29
2	55637	26 35

Ключ