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

Задания

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой  — 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока  — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, то есть не являющиеся выигрышными независимо от игры противника.

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

—  Петя не может выиграть за один ход;

—  Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Решение. Из хода решения предыдущего задания можно заключить, что значения S 35 и 36 не подходят, поскольку в этом случае Петя может выиграть своим первым ходом. Рассмотрим значение S  =  34. В этом случае Петя своим первым ходом может добавить в первую кучу один камень и получить кучу (8, 34). После первого хода Вани может возникнуть одна из четырёх позиций: (9, 34), (8, 35), (16, 34), (8, 68). Во всех случаях Петя удваивает количество камней во второй куче и выигрывает своим вторым ходом.

Второе значение S  — 31. При S  =  31 Петя удваивает количество камней в первой куче и получает позицию (14, 31). После первого хода Вани может возникнуть одна из четырёх позиций: (15, 31), (14, 32), (28, 31), (14, 62). Во всех случаях Петя удваивает количество камней во второй куче и выигрывает своим вторым ходом.

Таким образом, ответ  —3134.

Ответ: 3134.

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

def f(x, y, h):

if h == 4 and x + y >= 77:

return 1

elif h == 4 and x + y < 77:

return 0

elif x + y >= 77 and h < 4:

return 0

else:

if h % 2 != 0:

return f(x + 1, y, h + 1) or f(x, y + 1, h + 1) or f(x * 2, y, h + 1) or f(x, y * 2, h + 1) # стратегия победителя

else:

return f(x + 1, y, h + 1) and f(x, y + 1, h + 1) and f(x * 2, y, h + 1) and f(x, y * 2, h + 1) # стратегия проигравшего(любой ход)

for x in range(1, 70):

if f(x, 7, 1) == 1:

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

Приведём решение Виктории Зиберовой на языке Python.

def f (k1,k2, m):

if k1+k2 >= 77:

return m%2==0

if m==0:

return 0

h=[f(k1+1, k2, m-1),f(k1, k2+1, m-1), f(k1*2, k2, m-1), f(k1, k2*2, m-1)]

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

print('Задание 20:', (*[s for s in range (1, 70) if f(7,s,3) and not f(7, s, 1)]))

Приведём решение Георгия Вострикова на языке Python.

def f(k1, k2, hod):

# hod - номер хода. 1 - первый ход Пети, 2 - первый ход Вани, 3 - второй ход Пети, 4 - второй ход Вани

if hod == who_win and k1 + k2 >= win_sum:

# нужный игрок победил на нужном ходе

return 1

elif hod == who_win and k1 + k2 < win_sum:

# нужный игрок не победил на нужном ходе

return 0

elif hod < who_win and k1 + k2 >= win_sum:

# Петя или Ваня победил раньше времени

if ZADANIE != 21:

return 0

elif hod == who_win-2:

# в №21 допускаем победу Вани первым ходом(раньше времени, когда hod == 3)

return 1

# дальше начинается сам ход игрока

# ПРИМЕР: если hod = 3, то выше мы проверили не победил ли Ваня после своего первого хода

# если ещё не победил, тогда уже делаем второй ход Пети

else:

# hod - чётный, значит, сейчас ходит Ваня, иначе(нечёт) Петя

if hod % 2 == 0:

# действия Вани с кучами (по условию: k1/k2 + 1 и k1/k2 * 2)

if ZADANIE == 19 or ZADANIE == 21:

# играем за Ваню, подойдёт любое удобное дейтсвие(or)

return f(k1, k2 + sum2, hod + 1) or f(k1 + sum1, k2, hod + 1) or f(k1, k2 * x2, hod + 1) or f(k1 * x1, k2, hod + 1)

elif ZADANIE == 20:

# играем против Вани, проверяем все его возможные действия(and)

return f(k1, k2 + sum2, hod + 1) and f(k1 + sum1, k2, hod + 1) and f(k1, k2 * x2, hod + 1) and f(k1 * x1, k2, hod + 1)

else:

# действия Пети с кучами (по условию: k1/k2 + 1 и k1/k2 * 2)

if ZADANIE == 19 or ZADANIE == 20:

# играем против Пети или за Петю, подойдёт любое неудачное/удачное действие Пети(or)

return f(k1, k2 + sum2, hod + 1) or f(k1 + sum1, k2, hod + 1) or f(k1, k2 * x2, hod + 1) or f(k1 * x1, k2, hod + 1)

elif ZADANIE == 21:

# играем против Пети, проверяем все его возможные действия(and) для победы Вани 2ым ходом

if who_win == 5:

return f(k1, k2 + sum2, hod + 1) and f(k1 + sum1, k2, hod + 1) and f(k1, k2 * x2, hod + 1) and f(k1 * x1, k2, hod + 1)

elif who_win == 3:

# играем против Пети: проверяем, что не при любых ходах Пети, Ваня может выиграть первым ходом

if ((f(k1, k2 + sum2, hod + 1) + f(k1 + sum1, k2, hod + 1) + f(k1, k2 * x2, hod + 1) + f(k1 * x1, k2, hod + 1)) < kol):

return 1

# УСЛОВИЯ ЗАДАЧИ ------------------------------------------------

sum1 = 1 # сколько можно прибавлять в 1ую кучу

sum2 = 1 # сколько можно прибавлять во 2ую кучу

x1 = 2 # во сколько раз можно умножать 1ую кучу

x2 = 2 # во сколько раз можно умножать 2ую кучу

kol = 4 # количество вариантов действий с кучами

k1 = 7 # количество камней в 1ой куче

win_sum = 77 # общая сумма камней от которой начинается победа

k2_max = 69 # максимальное S(количество камней во 2ой куче)

# НОМЕР ЗАДАЧИ --------------------------------------------------

ZADANIE = 20 # для какого задания программа (19, 20 или 21)

if ZADANIE == 19:

# who_win - кто должен выиграть и каким ходом?

who_win = 3 # №19 - Ваня первым ходом

elif ZADANIE == 20:

who_win = 4 # №20 - Петя вторым ходом

elif ZADANIE == 21:

who_win = 5 # №21 - Ваня вторым ходом

for k2 in range(1, k2_max):

if f(k1, k2, 1) == 1:

if ZADANIE == 21:

who_win = 3 # проверяем, что не при любых ходах Пети, Ваня может выиграть первым ходом

if f(k1, k2, 1) == 1:

print(k2)

break

else:

print(k2)

if ZADANIE != 20:

break

№ п/п	№ задания	Ответ
1	27417	3134

Ключ