Задания
Версия для печати и копирования в MS Word

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

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

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

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

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

Спрятать решение

Ре­ше­ние.

За­ме­тим, что игра долж­на за­кон­чить­ся в 2 хода. Ми­ни­маль­ное зна­че­ние ко­ли­че­ства кам­ней в обеих кучах, при ко­то­ром игра за­кан­чи­ва­ет­ся,  — 77. Эта си­ту­а­ция воз­мож­на, на­при­мер, когда в пер­вой куче 7 кам­ней, а во вто­рой  — 70. Зна­чит, чтобы Ваня мог вы­иг­рать своим пер­вым ходом, ко­ли­че­ство кам­ней во вто­рой куче долж­но быть ≥35. По­сколь­ку удва­и­ва­ни­ем число 35 по­лу­чить нель­зя, после пер­во­го хода Пети во вто­рой куче долж­но по­лу­чить­ся 36 кам­ней. Это воз­мож­но при зна­че­нии S  =  18. При таком ми­ни­маль­ном зна­че­нии S Ваня вы­иг­ра­ет своим пер­вым ходом после не­удач­но­го хода Пети.

 

Ответ: 18.

 

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

def f(x, y, h):

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

return 1

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

return 0

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

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) or f(x, y + 1, h + 1) or f(x * 2, y, h + 1) or f(x, y * 2, h + 1) # стра­те­гия про­иг­рав­ше­го(не­удач­ный ход)

 

for x in range(1, 70):

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

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

break

 

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

from functools import lru_cache

def moves(h):

a, b = h

return (a+1, b), (a, b+1), (a*2, b), (b*2, a)

@lru_cache(None)

def game(h):

if sum(h) >= 77: return 'W'

if any(game(m) == 'W' for m in moves(h)): return 'P1'

if any(game(m) == 'P1' for m in moves(h)): return 'V1'

for s in range(1, 70):

if game((7, s)) == 'V1':

print(s)

break

 

При­ведём ре­ше­ние Глеба Гриш­ко на языке Python.

def f(a,b,m):

if a+b>=77:

return m%2==0

if m==0:

return 0

h = [f(a+1,b,m-1),f(a*2,b,m-1),f(a,b+1,m-1),f(a,b*2,m-1)]

return any(h) if (m-1)%2==0 else any(h)

print(min([s for s in range(1,70) if not f(7,s,1) and f(7,s,2)]))

 

При­ведём ре­ше­ние Ге­ор­гия Востри­ко­ва на языке 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 = 19 # для ка­ко­го за­да­ния про­грам­ма (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

Источник: Де­мон­стра­ци­он­ная вер­сия ЕГЭ−2021 по ин­фор­ма­ти­ке
Раздел кодификатора ФИПИ: 1.5.2 Це­поч­ки, де­ре­вья, спис­ки, графы, мат­ри­цы, псев­до­слу­чай­ные по­сле­до­ва­тель­но­сти
Спрятать решение · Помощь
1

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

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

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

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

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

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

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

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

Решение · Помощь
2

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

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

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

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

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

—  у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети;

—  у Вани нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом.

Решение · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026