Дано A = EA₁₆, B = 354₈. Какое из чисел C, за­пи­сан­ных в дво­ич­ной си­сте­ме, от­ве­ча­ет усло­вию A < C < B?

1)  11101100₂

2)  11101011₂

3)  11101010₂

4)  11101110₂

Между населёнными пунк­та­ми А, В, С, D, Е, F по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых при­ве­де­на в таб­ли­це. (От­сут­ствие числа в таб­ли­це озна­ча­ет, что пря­мой до­ро­ги между пунк­та­ми нет.)

Опре­де­ли­те длину крат­чай­ше­го пути между пунк­та­ми А и F (при усло­вии, что пе­ре­дви­гать­ся можно толь­ко по по­стро­ен­ным до­ро­гам).

Дан фраг­мент таб­ли­цы ис­тин­но­сти вы­ра­же­ния F:

Каким вы­ра­же­ни­ем может быть F?

1)  x1 ∧ ¬х2 ∧ хЗ ∧ ¬х4 ∧ х5 ∧ х6 ∧ ¬х7 ∧ х8

2) ¬x1 ∨ ¬х2 ∨ ¬хЗ ∨ х4 ∨ х5 ∨ х6 ∨ х7 ∨ х8

3)  x1 ∧ х2 ∧ хЗ ∧ ¬х4 ∧ ¬х5 ∧ ¬х6 ∧ ¬х7 ∧ ¬х8

4)  x1 ∨ ¬х2 ∨ хЗ ∨ ¬х4 ∨ ¬х5 ∨ х6 ∨ ¬х7 ∨ ¬х8

Для груп­по­вых опе­ра­ций с фай­ла­ми ис­поль­зу­ют­ся маски имён фай­лов. Маска пред­став­ля­ет собой по­сле­до­ва­тель­ность букв, цифр и про­чих до­пу­сти­мых в име­нах фай­лов сим­во­лов, в ко­то­рых также могут встре­чать­ся сле­ду­ю­щие сим­во­лы.

Сим­вол «?» (во­про­си­тель­ный знак) озна­ча­ет ровно один про­из­воль­ный сим­вол.

Сим­вол «*» (звёздоч­ка) озна­ча­ет любую по­сле­до­ва­тель­ность сим­во­лов про­из­воль­ной длины, в том числе «*» может за­да­вать и пу­стую по­сле­до­ва­тель­ность. В ка­та­ло­ге на­хо­дит­ся 6 фай­лов:

iren.dat

iren.data

bret.dat

grem.dat

ren.dat

arena.dat

Опре­де­ли­те, по какой из масок из них будет ото­бра­на ука­зан­ная груп­па фай­лов:

iren.dat

bret.dat

grem.dat

ren.dat

1)  *re?.dat

2)  *?re?*.*?dat?*

3)  ?re*.dat

4)  *re?.dat?

В не­ко­то­рой ин­фор­ма­ци­он­ной си­сте­ме ин­фор­ма­ция ко­ди­ру­ет­ся дво­ич­ны­ми ше­сти­раз­ряд­ны­ми сло­ва­ми. При пе­ре­да­че дан­ных воз­мож­ны их ис­ка­же­ния, по­это­му в конец каж­до­го слова до­бав­ля­ет­ся седь­мой (кон­троль­ный) раз­ряд таким об­ра­зом, чтобы сумма раз­ря­дов но­во­го слова, счи­тая кон­троль­ный, была чётной. На­при­мер, к слову 110011 спра­ва будет до­бав­лен 0, а к слову 101100  — 1.

После приёма слова про­из­во­дит­ся его об­ра­бот­ка. При этом про­ве­ря­ет­ся сумма его раз­ря­дов, вклю­чая кон­троль­ный. Если она нечётна, это озна­ча­ет, что при пе­ре­да­че этого слова про­изошёл сбой, и оно ав­то­ма­ти­че­ски за­ме­ня­ет­ся на за­ре­зер­ви­ро­ван­ное слово 0000000. Если она чётна, это озна­ча­ет, что сбоя не было или сбоев было боль­ше од­но­го. В этом слу­чае при­ня­тое слово не из­ме­ня­ет­ся.

Ис­ход­ное со­об­ще­ние

1010101 0100100 1101001

было при­ня­то в виде

1010001 0100100 1100000.

Как будет вы­гля­деть при­ня­тое со­об­ще­ние после об­ра­бот­ки?

1)  0000000 0100100 0000000

2)  1010101 0000000 1101001

3)  0000000 0100100 1100000

4)  1010101 0100100 0000000

Ниже пред­став­ле­ны две таб­ли­цы из базы дан­ных. Каж­дая стро­ка таб­ли­цы 2 со­дер­жит ин­фор­ма­цию о ребёнке и об одном из его ро­ди­те­лей. Ин­фор­ма­ция пред­став­ле­на зна­че­ни­ем поля ID в со­от­вет­ству­ю­щей стро­ке таб­ли­цы 1. Опре­де­ли­те на ос­но­ва­нии при­ведённых дан­ных фа­ми­лию и ини­ци­а­лы пле­мян­ни­цы Ерёма А. И. По­яс­не­ние: пле­мян­ни­цей счи­та­ет­ся дочь брата или сест­ры.

1)  Пет­рен­ко П. И.

2)  Грач Н. А.

3)  Крот П. А.

4)  Клыч­ко А. П.

Коле нужно с по­мо­щью элек­трон­ных таб­лиц по­стро­ить таб­ли­цу сло­же­ния чисел от 14 до 17.

Для этого сна­ча­ла в диа­па­зо­нах В1:Е1 и А2:А5 он за­пи­сал числа от 14 до 17. Затем в ячей­ку Е2 за­пи­сал фор­му­лу сло­же­ния, после чего ско­пи­ро­вал её во все ячей­ки диа­па­зо­на В2:Е5. В итоге на экра­не по­лу­чил­ся фраг­мент таб­ли­цы сло­же­ния (см. рис.).

Какая фор­му­ла была за­пи­са­на в ячей­ке Е2?

1)  =$Е1+А$2

2)  =Е1+А2

3)  =Е$1+А$2

4)  =Е$1+$А2

Про­из­во­дит­ся четырёхка­наль­ная (квад­ро) зву­ко­за­пись с ча­сто­той дис­кре­ти­за­ции 64 кГц и 32-бит­ным раз­ре­ше­ни­ем. За­пись длит­ся 1 ми­ну­ту, её ре­зуль­та­ты за­пи­сы­ва­ют­ся в файл, сжа­тие дан­ных не про­из­во­дит­ся. Какая из при­ведённых ниже ве­ли­чин наи­бо­лее близ­ка к раз­ме­ру по­лу­чен­но­го файла?

1)  59 Мбайт

2)  107 Мбайт

3)  157 Мбайт

4)  203 Мбайт

Для пе­ре­да­чи дан­ных по ка­на­лу связи ис­поль­зу­ет­ся 5-би­то­вый код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б и В, ко­то­рые ко­ди­ру­ют­ся сле­ду­ю­щи­ми ко­до­вы­ми сло­ва­ми:

При пе­ре­да­че воз­мож­ны по­ме­хи. Од­на­ко не­ко­то­рые ошиб­ки можно по­пы­тать­ся ис­пра­вить. Любые два из этих трёх ко­до­вых слов от­ли­ча­ют­ся друг от друга не менее чем в трёх по­зи­ци­ях. По­это­му если при пе­ре­да­че слова про­изо­шла ошиб­ка не более чем в одной по­зи­ции, то можно сде­лать обос­но­ван­ное пред­по­ло­же­ние о том, какая буква пе­ре­да­ва­лась. (Го­во­рят, что «код ис­прав­ля­ет одну ошиб­ку».) На­при­мер, если по­лу­че­но ко­до­вое слово 10110, счи­та­ет­ся, что пе­ре­да­ва­лась буква А. (От­ли­чие от ко­до­во­го слова для А толь­ко в одной по­зи­ции, для осталь­ных ко­до­вых слов от­ли­чий боль­ше.) Если при­ня­тое ко­до­вое слово от­ли­ча­ет­ся от ко­до­вых слов для букв А, Б, В более чем в одной по­зи­ции, то счи­та­ет­ся, что про­изо­шла ошиб­ка (она обо­зна­ча­ет­ся 'х').

По­лу­че­но со­об­ще­ние 10001 11010 10100 10110. Де­ко­ди­руй­те это со­об­ще­ние  — вы­бе­ри­те пра­виль­ный ва­ри­ант.

1)  хххх

2)  БхВх

3)  БАВА

4)  БхВА

На чис­ло­вой пря­мой даны два от­рез­ка: Р = [3, 38] и Q = [21, 57]. Вы­бе­ри­те из пред­ло­жен­ных от­рез­ков такой от­ре­зок А, что ло­ги­че­ское вы­ра­же­ние

тож­де­ствен­но ис­тин­но, то есть при­ни­ма­ет зна­че­ние 1 при любом зна­че­нии пе­ре­мен­ной х.

1)  [6,20]

2)  [22,35]

3)  [40,60]

4)  [20,40]

В ве­ло­к­рос­се участ­ву­ют 108 спортс­ме­нов. Спе­ци­аль­ное устрой­ство ре­ги­стри­ру­ет про­хож­де­ние каж­дым из участ­ни­ков про­ме­жу­точ­но­го фи­ни­ша, за­пи­сы­вая его номер с ис­поль­зо­ва­ни­ем ми­ни­маль­но воз­мож­но­го ко­ли­че­ства бит, оди­на­ко­во­го для каж­до­го из спортс­ме­нов. Какой объём па­мя­ти будет ис­поль­зо­ван устрой­ством, когда про­ме­жу­точ­ный финиш про­шли 96 ве­ло­си­пе­ди­стов? (Ответ дайте в бай­тах.)

В про­грам­ме опи­са­ны од­но­мер­ный це­ло­чис­лен­ный мас­сив А с ин­дек­са­ми от 0 до 10 и це­ло­чис­лен­ные пе­ре­мен­ные i и t. Ниже пред­став­лен фраг­мент этой про­грам­мы, за­пи­сан­ный на раз­ных язы­ках про­грам­ми­ро­ва­ния.

Чему ока­жут­ся равны эле­мен­ты этого мас­си­ва после вы­пол­не­ния фраг­мен­та про­грам­мы?

1)  10 0 0 0 0 0 0 0 0 0 0

2)  10 2 3 4 5 6 7 8 9 10 10

3)  10 10 10 10 10 10 10 10 10 10 10

4)  10 0 1 2 3 4 5 6 7 8 9

Си­сте­ма ко­манд ис­пол­ни­те­ля РОБОТ, «жи­ву­ще­го» в пря­мо­уголь­ном ла­би­рин­те на клет­ча­той плос­ко­сти, вклю­ча­ет в себя 4 ко­ман­ды-при­ка­за и 4 ко­ман­ды про­вер­ки усло­вия.

Ко­ман­ды-при­ка­зы:

При вы­пол­не­нии любой из этих ко­манд РОБОТ пе­ре­ме­ща­ет­ся на одну клет­ку со­от­вет­ствен­но: вверх ↑, вниз ↓, влево ←, впра­во →.

Если РОБОТ начнёт дви­же­ние в сто­ро­ну на­хо­дя­щей­ся рядом с ним стены, то он раз­ру­шит­ся, и про­грам­ма прервётся.

Дру­гие 4 ко­ман­ды про­ве­ря­ют ис­тин­ность усло­вия от­сут­ствия стены у каж­дой сто­ро­ны той клет­ки, где на­хо­дит­ся РОБОТ:

Цикл

ПОКА усло­вие

по­сле­до­ва­тель­ность ко­манд

КОНЕЦ ПОКА

вы­пол­ня­ет­ся, пока усло­вие ис­тин­но. В кон­струк­ции

ЕСЛИ усло­вие

ТО ко­ман­да1

ИНАЧЕ ко­ман­да2

КОНЕЦ ЕСЛИ

вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но) или ко­ман­да2 (если усло­вие ложно).

Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка A6)?

НА­ЧА­ЛО

ПОКА снизу сво­бод­но ИЛИ слева сво­бод­но

ЕСЛИ снизу сво­бод­но

ТО вниз

ИНАЧЕ влево

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

ис­пол­ни­те­ля Каль­ку­ля­тор две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

1. при­бавь 2,

2.  умножь на 5.

Вы­пол­няя первую из них, Каль­ку­ля­тор при­бав­ля­ет к числу на экра­не 2, а вы­пол­няя вто­рую, умно­жа­ет его на 5. За­пи­ши­те по­ря­док ко­манд в про­грам­ме, ко­то­рая пре­об­ра­зу­ет число 2 в число 16 и со­дер­жит не более 4 ко­манд. Ука­зы­вай­те лишь но­ме­ра ко­манд.

(На­при­мер, про­грам­ма 2121  — это про­грам­ма

умножь на 5,

при­бавь 2,

умножь на 5,

при­бавь 2.

Эта про­грам­ма пре­об­ра­зу­ет число 1 в число 37.)

Опре­де­ли­те зна­че­ние пе­ре­мен­ной с после вы­пол­не­ния сле­ду­ю­ще­го фраг­мен­та про­грам­мы {за­пи­сан­но­го ниже на раз­ных язы­ках про­грам­ми­ро­ва­ния). Ответ за­пи­ши­те в виде це­ло­го числа.

Дан фраг­мент элек­трон­ной таб­ли­цы:

Какое целое число долж­но быть за­пи­са­но в ячей­ке B1, чтобы по­стро­ен­ная после вы­пол­не­ния вы­чис­ле­ний диа­грам­ма по зна­че­ни­ям диа­па­зо­на ячеек А2:С2 со­от­вет­ство­ва­ла ри­сун­ку?

Из­вест­но, что все зна­че­ния диа­па­зо­на, по ко­то­рым по­стро­е­на диа­грам­ма, имеют один и тот же знак.

Для пе­ре­да­чи ава­рий­ных сиг­на­лов до­го­во­ри­лись ис­поль­зо­вать спе­ци­аль­ные цвет­ные сиг­наль­ные ра­ке­ты, за­пус­ка­е­мые по­сле­до­ва­тель­но. Одна по­сле­до­ва­тель­ность ракет  — один сиг­нал; в каком по­ряд­ке идут цвета  — су­ще­ствен­но. Какое ко­ли­че­ство раз­лич­ных сиг­на­лов можно пе­ре­дать при по­мо­щи за­пус­ка ровно четырёх таких сиг­наль­ных ракет, если в за­па­се име­ют­ся ра­ке­ты пяти раз­лич­ных цве­тов (ракет каж­до­го вида не­огра­ни­чен­ное ко­ли­че­ство, цвет ракет в по­сле­до­ва­тель­но­сти может по­вто­рять­ся)?

Опре­де­ли­те число, ко­то­рое будет на­пе­ча­та­но в ре­зуль­та­те вы­пол­не­ния про­грам­мы (за­пи­сан­ной ниже на раз­ных язы­ках про­грам­ми­ро­ва­ния).

Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n  — на­ту­раль­ное число, задан сле­ду­ю­щи­ми со­от­но­ше­ни­я­ми:

F(n)  =  n + 4 при n ≤ 2;

F(n)  =  F(n − 1) + F(n − 2) при n > 2.

Чему равно зна­че­ние функ­ции F(6)? В от­ве­те за­пи­ши­те толь­ко на­ту­раль­ное число.

За­пи­ши­те де­ся­тич­ное число 38 в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 5. Ос­но­ва­ние си­сте­мы счис­ле­ния (ниж­ний ин­декс после числа) пи­сать не нужно.

Ниже на пяти язы­ках за­пи­сан ал­го­ритм. По­лу­чив на вход число x, этот ал­го­ритм пе­ча­та­ет два числа: a и b. Ука­жи­те наи­мень­шее из таких чисел x, при вводе ко­то­рых ал­го­ритм пе­ча­та­ет сна­ча­ла 11, а потом 5.

На ри­сун­ке  — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, И, К, Л. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Л?

До­ку­мент объёмом 16 Мбайт можно пе­ре­дать с од­но­го ком­пью­те­ра на дру­гой двумя спо­со­ба­ми.

А.  Сжать ар­хи­ва­то­ром, пе­ре­дать архив по ка­на­лу связи, рас­па­ко­вать.

Б.  Пе­ре­дать по ка­на­лу связи без ис­поль­зо­ва­ния ар­хи­ва­то­ра.

Какой спо­соб быст­рее и на­сколь­ко, если:

 ·  сред­няя ско­рость пе­ре­да­чи дан­ных по ка­на­лу связи со­став­ля­ет 2²¹ бит в се­кун­ду;

 ·  объём сжа­то­го ар­хи­ва­то­ром до­ку­мен­та равен 75% ис­ход­но­го;

 ·  время, тре­бу­е­мое на сжа­тие до­ку­мен­та,  — 14 се­кунд, на рас­па­ков­ку  — 3 се­кун­ды?

В от­ве­те на­пи­ши­те букву А, если быст­рее спо­соб А, или Б, если быст­рее спо­соб Б. Сразу после буквы на­пи­ши­те число, обо­зна­ча­ю­щее, на сколь­ко се­кунд один спо­соб быст­рее дру­го­го. Так, на­при­мер, если спо­соб Б быст­рее спо­со­ба А на 23 се­кун­ды, в от­ве­те нужно на­пи­сать Б23. Еди­ни­цы из­ме­ре­ния «се­кунд», «сек.», «с.» к от­ве­ту до­бав­лять не нужно.

В тер­ми­но­ло­гии сетей TCP/⁠IP мас­кой сети на­зы­ва­ет­ся дво­ич­ное число, опре­де­ля­ю­щее, какая часть IP-⁠ад­ре­са узла сети от­но­сит­ся к ад­ре­су сети, а какая  — к ад­ре­су са­мо­го узла в этой сети. Обыч­но маска за­пи­сы­ва­ет­ся по тем же пра­ви­лам, что и IP-⁠адрес. Адрес сети по­лу­ча­ет­ся в ре­зуль­та­те при­ме­не­ния по­раз­ряд­ной конъ­юнк­ции к за­дан­но­му IP-⁠ад­ре­су узла и маске. По за­дан­ным IP-ад­ре­су узла и маске опре­де­ли­те адрес сети.

IP-⁠адрес узла: 130.132.131.64

Маска: 255.255.192.0

При за­пи­си от­ве­та вы­бе­ри­те из при­ведённых в таб­ли­це чисел че­ты­ре эле­мен­та IP-⁠ад­ре­са сети и за­пи­ши­те в нуж­ном по­ряд­ке со­от­вет­ству­ю­щие им буквы без ис­поль­зо­ва­ния точек.

При­мер.

Пусть ис­ко­мый IP-⁠адрес: 192.168.128.0 и дана таб­ли­ца:

В этом слу­чае пра­виль­ный ответ будет за­пи­сан в виде: HBAF.

В языке за­про­сов по­ис­ко­во­го сер­ве­ра для обо­зна­че­ния ло­ги­че­ской опе­ра­ции «ИЛИ» ис­поль­зу­ет­ся сим­вол «|», а для ло­ги­че­ской опе­ра­ции «И» – сим­вол «&». В таб­ли­це при­ве­де­ны за­про­сы и ко­ли­че­ство най­ден­ных по ним стра­ниц не­ко­то­ро­го сег­мен­та сети Ин­тер­нет:

Ком­пью­тер пе­ча­та­ет ко­ли­че­ство стра­ниц (в ты­ся­чах), ко­то­рое будет най­де­но по сле­ду­ю­ще­му за­про­су: Ев­клид & (Ари­сто­тель|Пла­тон) Ука­жи­те целое число, ко­то­рое на­пе­ча­та­ет ком­пью­тер. Счи­та­ет­ся, что все за­про­сы вы­пол­ня­лись прак­ти­че­ски од­но­вре­мен­но, так что набор стра­ниц, со­дер­жа­щих все ис­ко­мые слова, не из­ме­нял­ся за время вы­пол­не­ния за­про­сов.

У ис­пол­ни­те­ля Удво­и­тель две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

1.  при­бавь 1,

2.  при­бавь 5.

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 1, вто­рая уве­ли­чи­ва­ет его на 5. Про­грам­ма для Удво­и­те­ля  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко есть про­грамм, ко­то­рые число 2 пре­об­ра­зу­ют в число 16?

На­пи­ши­те в от­ве­те число, ко­то­рое будет на­пе­ча­та­но в ре­зуль­та­те вы­пол­не­ния сле­ду­ю­ще­го ал­го­рит­ма (для Ва­ше­го удоб­ства ал­го­ритм пред­став­лен на четырёх язы­ках).

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x₁, x₂, ... x₈, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

¬(x₁ ≡ x₂) ∧ ( (x₁ ∧ ¬x₃) ∨ (¬x₁ ∧ x₃) ) = 0

¬(x₂ ≡ x₃) ∧ ( (x₂ ∧ ¬x₄) ∨ (¬x₂ ∧ x₄) ) = 0

...

¬(x₆ ≡ x₇) ∧ ( (x₆ ∧ ¬x₈) ∨ (¬x₆ ∧ x₈) ) = 0

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x₁, x₂, … x₈ при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Тре­бо­ва­лось на­пи­сать про­грам­му, при вы­пол­не­нии ко­то­рой с кла­ви­а­ту­ры счи­ты­ва­ет­ся на­ту­раль­ное число N, не пре­вос­хо­дя­щее 10⁹, и вы­во­дит­ся мак­си­маль­ная цифра этого числа. Про­грам­мист то­ро­пил­ся и на­пи­сал про­грам­му не­пра­виль­но. (Ниже для Ва­ше­го удоб­ства про­грам­ма пред­став­ле­на на четырёх язы­ках про­грам­ми­ро­ва­ния.)

По­сле­до­ва­тель­но вы­пол­ни­те сле­ду­ю­щее.

1.  На­пи­ши­те, что вы­ве­дет эта про­грам­ма при вводе числа 738.

2.  Най­ди­те все ошиб­ки в этой про­грам­ме (их может быть одна или не­сколь­ко). Для каж­дой ошиб­ки:

1) вы­пи­ши­те стро­ку, в ко­то­рой сде­ла­на ошиб­ка;

2) ука­жи­те, как ис­пра­вить ошиб­ку,  — при­ве­ди­те пра­виль­ный ва­ри­ант стро­ки.

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

Дан це­ло­чис­лен­ный мас­сив из 20 эле­мен­тов. Эле­мен­ты мас­си­ва могут при­ни­мать целые зна­че­ния от 0 до 10000 вклю­чи­тель­но. Опи­ши­те на есте­ствен­ном языке или на одном из язы­ков про­грам­ми­ро­ва­ния ал­го­ритм, поз­во­ля­ю­щий найти и вы­ве­сти мак­си­маль­ное зна­че­ние среди трёхзнач­ных эле­мен­тов мас­си­ва, не де­ля­щих­ся на 7. Если в ис­ход­ном мас­си­ве нет эле­мен­та, зна­че­ние ко­то­ро­го яв­ля­ет­ся трёхзнач­ным чис­лом и при этом не крат­но 7, то вы­ве­сти со­об­ще­ние «Не най­де­но».

Ис­ход­ные дан­ные объ­яв­ле­ны так, как по­ка­за­но ниже на при­ме­рах для не­ко­то­рых язы­ков про­грам­ми­ро­ва­ния и есте­ствен­но­го языка. За­пре­ща­ет­ся ис­поль­зо­вать пе­ре­мен­ные, не опи­сан­ные ниже, но раз­ре­ша­ет­ся не ис­поль­зо­вать не­ко­то­рые из опи­сан­ных пе­ре­мен­ных.

В ка­че­стве от­ве­та Вам не­об­хо­ди­мо при­ве­сти фраг­мент про­грам­мы (или опи­са­ние ал­го­рит­ма на есте­ствен­ном языке), ко­то­рый дол­жен на­хо­дить­ся на месте мно­го­то­чия. Вы мо­же­те за­пи­сать ре­ше­ние также на дру­гом языке про­грам­ми­ро­ва­ния (ука­жи­те на­зва­ние и ис­поль­зу­е­мую вер­сию языка про­грам­ми­ро­ва­ния, на­при­мер, Free Pascal 2.4) или в виде блок-схемы. В этом слу­чае Вы долж­ны ис­поль­зо­вать те же самые ис­ход­ные дан­ные и пе­ре­мен­ные, какие были пред­ло­же­ны в усло­вии (на­при­мер, в об­раз­це, за­пи­сан­ном на есте­ствен­ном языке).

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в кучу один или два камня или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, имея кучу из 15 кам­ней, за один ход можно по­лу­чить кучу из 16, 17 или 30 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 40. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 40 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 39.

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

Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.

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

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

2.  Ука­жи­те два таких зна­че­ния S, при ко­то­рых у Пети есть вы­иг­рыш­ная стра­те­гия, причём (а) Петя не может вы­иг­рать за один ход и (б) Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня. Для каж­до­го ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.

3.  Ука­жи­те зна­че­ние S, при ко­то­ром:

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

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

Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вани. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при этой вы­иг­рыш­ной стра­те­гии Вани (в виде ри­сун­ка или таб­ли­цы). На рёбрах де­ре­ва ука­зы­вай­те, кто де­ла­ет ход, в узлах  — ко­ли­че­ство кам­ней в куче.

По ка­на­лу связи пе­ре­даётся по­сле­до­ва­тель­ность по­ло­жи­тель­ных целых чисел, все числа не пре­вы­ша­ют 1000. Ко­ли­че­ство чисел из­вест­но, но может быть очень ве­ли­ко. Затем пе­ре­даётся кон­троль­ное зна­че­ние по­сле­до­ва­тель­но­сти  — наи­боль­шее число R, удо­вле­тво­ря­ю­щее сле­ду­ю­щим усло­ви­ям:

1)  R  — про­из­ве­де­ние двух раз­лич­ных пе­ре­дан­ных эле­мен­тов по­сле­до­ва­тель­но­сти («раз­лич­ные» озна­ча­ет, что не рас­смат­ри­ва­ют­ся квад­ра­ты пе­ре­дан­ных чисел, про­из­ве­де­ния раз­лич­ных эле­мен­тов по­сле­до­ва­тель­но­сти, рав­ных по ве­ли­чи­не, до­пус­ка­ют­ся);

2)  R де­лит­ся на 14.

Если та­ко­го числа R нет, то кон­троль­ное зна­че­ние по­ла­га­ет­ся рав­ным 0. В ре­зуль­та­те помех при пе­ре­да­че как сами числа, так и кон­троль­ное зна­че­ние могут быть ис­ка­же­ны.

На­пи­ши­те про­грам­му (ука­жи­те ис­поль­зу­е­мую вер­сию языка про­грам­ми­ро­ва­ния, на­при­мер, Borland Pascal 7.0), ко­то­рая будет про­ве­рять пра­виль­ность кон­троль­но­го зна­че­ния. Про­грам­ма долж­на на­пе­ча­тать отчёт по сле­ду­ю­щей форме:

Вы­чис­лен­ное кон­троль­ное зна­че­ние: ...

Кон­троль прой­ден (или  — Кон­троль не прой­ден)

Перед тек­стом про­грам­мы крат­ко опи­ши­те ис­поль­зу­е­мый Вами ал­го­ритм ре­ше­ния.

На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство чисел N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 1000. В по­след­ней стро­ке за­пи­са­но кон­троль­ное зна­че­ние.

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

Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б. Если ре­ше­ние од­но­го из за­да­ний не пред­став­ле­но, то счи­та­ет­ся, что оцен­ка за это за­да­ние со­став­ля­ет 0 бал­лов.

За­да­ние Б яв­ля­ет­ся услож­нен­ным ва­ри­ан­том за­да­ния А, оно со­дер­жит до­пол­ни­тель­ные тре­бо­ва­ния к про­грам­ме. Перед про­грам­мой ука­жи­те вер­сию языка про­грам­ми­ро­ва­ния.

А. На­пи­ши­те на любом языке про­грам­ми­ро­ва­ния про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, в ко­то­рой вход­ные дан­ные будут за­по­ми­нать­ся в мас­си­ве, после чего будут про­ве­ре­ны все воз­мож­ные пары эле­мен­тов.

Обя­за­тель­но ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем за­да­ния А.

Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А – 2 балла.

Б. На­пи­ши­те про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, ко­то­рая будет эф­фек­тив­на как по вре­ме­ни, так и по па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству эле­мен­тов по­сле­до­ва­тель­но­сти N, т. е. при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз. Обя­за­тель­но ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем за­да­ния Б.

При­мер вход­ных дан­ных:

6

77

14

7

9

499

100

7700

При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных:

Вы­чис­лен­ное кон­троль­ное зна­че­ние: 7700

Кон­троль прой­ден