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

Задания

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

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

Решение. Такая ситуация возможна при S  =  46. Могут быть кучи (45, 44 и меньше), (46, 45 и меньше), (47, 46 и меньше) и (24, 25 и больше). Поскольку нам необходимо набрать наименьшее количество камней суммарно в двух кучах, то такая позиция (45, 1). Петя увеличит количество камней в большей куче на три и выиграет первым ходом.

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

from itertools import product as p

def Win(ma, mi, k):

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

return 0 if ma >= 48 or mi >= 48 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 >= 48 or mi >= 48 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('Задание 19:', min([x+y for x, y in p(range(1,48), repeat=2) if Win(x, y, 1)]))

Ответ: 46.

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

def game(p1, p2, mov):

if (p1 >= 48 or p2 >= 48) and mov == 2:

return 1

elif mov > 2:

return 0

else:

if p1 > p2:

return game(p1 + 1, p2, mov + 1) or game(p1 + 2, p2, mov + 1) or game(p1 + 3, p2, mov + 1) or game(p1, p2 * 2, mov + 1)

elif p1 == p2:

return game(p1 + 1, p2, mov + 1) or game(p1 + 2, p2, mov + 1) or game(p1 + 3, p2, mov + 1) or game(p1, p2 + 1, mov + 1) or game(p1, p2 + 2, mov + 1) or game(p1, p2 + 3, mov + 1)

else:

return game(p1, p2 + 1, mov + 1) or game(p1, p2 + 1, mov + 1) or game(p1, p2 + 3, mov + 1) or game(p1 * 2, p2, mov + 1)

sum = float('inf')

for i in range(1, 47):

for j in range(1, 47):

if game(i, j, 1) == 1:

sum = min(sum, i + j)

print(sum)

№ п/п	№ задания	Ответ
1	58486	46

Ключ