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

Задания

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

—  добавить в кучу один камень;

—  если количество камней в куче чётно, добавить половину имеющегося количества;

—  если количество камней в куче кратно трём, добавить треть имеющегося количества;

—  если количество камней в куче не кратно ни двум, ни трём, удвоить кучу.

Например, если в куче 5 камней, то за один ход можно получить 6 или 10 камней, а если в куче 6 камней, то за один ход можно получить 7, или 8, или 9 камней.

Игра завершается, когда количество камней в куче достигает 96.

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

В начале игры в куче было S камней, 1 ≤ S ≤ 95.

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

Решение. Такое значение S  — 48. Своим первым ходом Петя может получить позиции 49, 72 (так как число делится на 2) и 64 (так как число делится на 3). В случае позиции 49 Ваня удваивает количество камней в куче и выигрывает своим первым ходом (так как 49 не делится на 2 или 3). В случае позиции 72 или 64 Ваня добавляет половину камней в куче и выигрывает своим первым ходом (так как 72 и 52 делятся на 2).

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

def f(x, h):

if x >= 96:

return h % 2 == 0

if h == 0:

return 0

c = [f(x + 1, h - 1)]

if x % 2 == 0:

c += [f(x *3 // 2, h - 1)]

if x % 3 == 0:

c += [f(x *4 // 3, h - 1)]

if x % 2 != 0 and x % 3 != 0:

c += [f(x * 2, h - 1)]

return any (c) if h % 2 != 0 else all(c)

for x in range(1, 96):

if f(x, 2) == 1:

print("Задача 19: ", x)

break

Решим задание с помощью электронных таблиц.

В ячейку B1 введем максимальное значение камней в куче 95. В ячейке С3 будем подбирать количество камней в куче. В столбце D будем указывать ходы Пети, в столбце Е  — ходы Вани. Если ход невозможен пропишем отрицательное число камей, например −1000.

Для Пети пропишем следующие ходы:

В ячейку D3  — ход =C3+1;

В ячейку D7  — ход =ЕСЛИ(ОСТАТ(C3;2)=0;C3+C3*0,5;-1000);

В ячейку D11  — ход =ЕСЛИ(ОСТАТ(C3;3)=0;C3+C3*1/3;-1000);

В ячейку D15  — ход =ЕСЛИ(И(ОСТАТ(C3;2)<>0;ОСТАТ(C3;3)<>0);C3*2;-1000).

Для Вани пропишем ходы аналогично, соответственно ходам Пети.

Для столбца D зададим условное форматирование, если значение в ячейке больше ячейки B1, то красим ее в красный цвет. Для столбца Е зададим условное форматирование, если значение в ячейке больше ячейки B1, то красим ее в зеленый цвет.

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

Получим следующую таблицу и подходящее значение 48.

Файл с решением: Решение.xlsx

Ответ: 48.

№ п/п	№ задания	Ответ
1	63035	48

Ключ