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

Задания

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче 5 камней, а во второй  — 8 камней, будем обозначать такую позицию (5, 8). Петя первым ходом должен добавлять камни в первую кучу, он может получить позиции (6, 8), (7, 8) и (10, 8). Если Петя получает позиции (6, 8) и (7, 8), Ваня следующим ходом тоже должен добавлять камни в первую кучу, а если Петя получает позицию (10, 8), Ваня должен добавлять камни во вторую кучу, так как теперь она стала меньшей.

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

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

Решение. Такая ситуация возможна при S  =  55. При этом в одной из куч 12 камней. Петя может сделать следующие варианты: (13,55), (14,55) и (24,55). Во всех случаях Ваня увеличивает в два раза количество камней в меньшей куче и выигрывает свои первым ходом.

Ответ: 55.

Приведем решение Юрия Красильникова на языке Python.

def move(n,lim,s):

# n - номер хода, lim - ограничение на число ходов, s - числа камней в кучах (кортеж)

# Результат: 1 - выиграл первый игрок, 2 - второй, 0 - победителя нет

player = 2 - n%2# Текущий игрок

rival = 3-player# Противник

if sum(s) > 80:# Игра уже окончена

return rival# Выиграл сделавший предыдущий ход

if n > lim:# Превышен лимит ходов

return 0# Победитель не определен

s1,s2 = s# Распаковка позиции

pos = [(s1+1,s2),(s1+2,s2),(s1*2,s2)] if s1 < s2 else [(s1,s2+1),(s1,s2+2),(s1,s2*2)]

res = [move(n+1,lim,x) for x in pos]# Результаты ходов

if any([x == player for x in res]): # Есть выигрышный ход

return player

if all([x == rival for x in res]):# Все ходы проигрышные

return rival

return 0# Победитель не определен

print('#19:',*[s for s in range(1,69) if move(1,2,(12,s)) == 2])

print('#20:',*[s for s in range(1,69) if move(1,1,(12,s)) == 0 and move(1,3,(12,s)) == 1])

print('#21:',*[s for s in range(1,69) if move(1,2,(12,s)) == 0 and move(1,4,(12,s)) == 2])

Приведем решение Михаила Глинского на языке Python.

def F(a,b,n):

if n == 2 and a+b > 80: return 1

if n == 2 and a+b <= 80: return 0

if n == 1 and a+b > 80: return 0

else:

if n%2==1:

if a < b: return F(a+1,b,n+1) or F(a+2,b,n+1) or F(a*2,b,n+1)

else: return F(a,b+1,n+1) or F(a,b+2,n+1) or F(a,b*2,n+1)

if n%2==0:

if a < b: return F(a+1,b,n+1) and F(a+2,b,n+1) and F(a*2,b,n+1)

else: return F(a,b+1,n+1) and F(a,b+2,n+1) and F(a,b*2,n+1)

for s in range(1,69):

if F(12,s,0):

print(s)

break

№ п/п	№ задания	Ответ
1	51988	55

Ключ