За­да­ние 1

Найти сумму двух чисел и за­пи­сать ре­зуль­тат в дво­ич­ной си­сте­ме счис­ле­ния:

За­да­ние 2

Дан фраг­мент таб­ли­цы ис­тин­но­сти вы­ра­же­ния 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

За­да­ние 3

Между че­тырь­мя мест­ны­ми аэро­пор­та­ми: ЛЕС­НОЕ, СИ­НИ­ЦЫ­НО, АЛЕК­СЕ­ЕВСК и ЯБ­ЛО­НО­ВО, еже­днев­но вы­пол­ня­ют­ся авиа­рей­сы. При­ведён фраг­мент рас­пи­са­ния перелётов между ними:

Пу­те­ше­ствен­ник ока­зал­ся в аэро­пор­ту ЛЕС­НОЕ в пол­ночь. Опре­де­ли­те самое ран­нее время, когда он может по­пасть в аэро­порт ЯБ­ЛО­НО­ВО. Счи­та­ет­ся, что пу­те­ше­ствен­ник успе­ва­ет со­вер­шить пе­ре­сад­ку в аэро­пор­ту, если между вре­ме­нем при­ле­та в этот аэро­порт и вре­ме­нем вы­ле­та про­хо­дит не менее часа.

1) 13:20

2) 13:55

3) 14:05

4) 15:00

За­да­ние 4

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

Ру­ко­вод­ству­ясь при­ве­ден­ны­ми таб­ли­ца­ми, опре­де­ли­те мак­си­маль­но воз­мож­ное число со­труд­ни­ков, при­шед­ших на ра­бо­ту 2 ок­тяб­ря с 9:00 до 10:00, ко­то­рые могут на­хо­дить­ся в зоне А глав­но­го кор­пу­са.

1) 5

2) 3

3) 1

4) 0

За­да­ние 5

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

A — 11110,

Б — 00000,

В — 01011.

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

1) хВхБ

2) хххх

3) хВАБ

4) ВВАБ

За­да­ние 6

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

1. вычти 2

2. умножь на три

Пер­вая из них умень­ша­ет число на экра­не на 2, вто­рая – утра­и­ва­ет его. За­пи­ши­те по­ря­док ко­манд в про­грам­ме по­лу­че­ния из 11 числа 13, со­дер­жа­щей не более 5 ко­манд, ука­зы­вая лишь но­ме­ра ко­манд. (На­при­мер, 21211 – это про­грам­ма:

умножь на три

вычти 2

умножь на три

вычти 2

вычти 2,

ко­то­рая пре­об­ра­зу­ет число 2 в 8). (Если таких про­грамм более одной, то за­пи­ши­те любую из них.)

За­да­ние 7

В элек­трон­ной таб­ли­це зна­че­ние фор­му­лы =CУMM(B2:D2) равно 15. Чему равно зна­че­ние ячей­ки А2, если зна­че­ние фор­му­лы =CP3HAЧ(A2:D2) равно 4? Пу­стых ячеек в таб­ли­це нет.

1) 1

2) 5

3) 16

4) 20

За­да­ние 8

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

За­да­ние 9

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

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

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

Какой спо­соб быст­рее и на­сколь­ко, если: · сред­няя ско­рость пе­ре­да­чи дан­ных по ка­на­лу связи со­став­ля­ет 221 бит в се­кун­ду;

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

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

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

За­да­ние 10

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

За­да­ние 11

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­са­ны две ре­кур­сив­ные функ­ции: F и G.

Чему будет равно зна­че­ние, вы­чис­лен­ное при вы­пол­не­нии вы­зо­ва F(8)?

За­да­ние 12

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

IP-адрес узла: 129.131.130.64

Маска: 255.255.192.0

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

За­да­ние 13

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

1) 10 байт

2) 28 бит

3) 7 бит

4) 14 байт

За­да­ние 14

Ис­пол­ни­тель РОБОТ умеет пе­ре­ме­щать­ся по пря­мо­уголь­но­му ла­би­рин­ту, на­чер­чен­но­му на плос­ко­сти, раз­би­той на клет­ки. Между со­сед­ни­ми по сто­ро­нам клет­ка­ми может сто­ять стена.

Си­сте­ма ко­манд ис­пол­ни­те­ля РОБОТ со­дер­жит во­семь ко­манд. Че­ты­ре ко­ман­ды это ко­ман­ды-при­ка­зы: вверх,вниз, влево, впра­во.

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

Че­ты­ре ко­ман­ды про­ве­ря­ют ис­тин­ность усло­вия от­сут­ствия стены у каж­дой

сто­ро­ны той клет­ки, где на­хо­дит­ся РОБОТ: свер­ху сво­бод­но, снизу сво­бод­но, слева сво­бод­но, спра­ва сво­бод­но.

Цикл

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

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

КОНЕЦ ПОКА

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

В кон­струк­ции

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

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

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

КОНЕЦ ЕСЛИ

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

В кон­струк­ци­ях ПОКА и ЕСЛИ усло­вие может со­дер­жать ко­ман­ды-про­вер­ки, а также слова И, ИЛИ, НЕ, обо­зна­ча­ю­щие ло­ги­че­ские опе­ра­ции. Если РОБОТ начнёт дви­же­ние в сто­ро­ну на­хо­дя­щей­ся рядом с ним стены, то он раз­ру­шит­ся и про­грам­ма прервётся. Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в этой клет­ке и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)?

НА­ЧА­ЛО

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

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

ТО вниз

ИНАЧЕ впра­во

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

1) 9

2) 12

3) 18

4) 24

За­да­ние 15

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

За­да­ние 16

В си­сте­ме счис­ле­ния с не­ко­то­рым ос­но­ва­ни­ем число 12 за­пи­сы­ва­ет­ся в виде 110. Ука­жи­те это ос­но­ва­ние.

За­да­ние 17

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

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

За­да­ние 18

Какое из при­ве­ден­ных на­зва­ний жи­вот­ных удо­вле­тво­ря­ет ло­ги­че­ско­му усло­вию: В слове пять букв /\ Чет­вер­тая буква глас­ная?

1) Зебра

2) Слон

3) Кабан

4) Олень

За­да­ние 19

В про­грам­ме опи­сан од­но­мер­ный це­ло­чис­лен­ный мас­сив с ин­дек­са­ми от 0 до 10. Ниже пред­став­лен за­пи­сан­ный на раз­ных язы­ках про­грам­ми­ро­ва­ния,фраг­мент одной и той же про­грам­мы, об­ра­ба­ты­ва­ю­щей дан­ный мас­сив:

В на­ча­ле вы­пол­не­ния этого фраг­мен­та в мас­си­ве на­хо­ди­лись числа 0, 10, 20, 30, 40, 50, 60, 70, 80. 90, 100, т.е. A[0] = 0, A[1] = 10 и т. д. Чему будет равно зна­че­ние пе­ре­мен­ной s после вы­пол­не­ния дан­ной про­грам­мы?

1) 60

2) 100

3) 150

4) 550

За­да­ние 20

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

var x, a, b: integer;

begin

    readln(x);

    a:=0; b:=1;

    while x>0 do begin

        a:=a+1;

        b:=b*(x mod 10);

        x:= x div 10;

    end;

    writeln(a); write(b);

end.

За­да­ние 21

На­пи­ши­те в от­ве­те наи­мень­шее зна­че­ние вход­ной пе­ре­мен­ной k, при ко­то­ром про­грам­ма выдаёт тот же ответ, что и при вход­ном зна­че­нии k = 20. Для Ва­ше­го удоб­ства про­грам­ма при­ве­де­на на пяти язы­ках про­грам­ми­ро­ва­ния.

За­да­ние 22

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

За­да­ние 23

Сколь­ко раз­лич­ных ре­ше­ний имеет урав­не­ние (K ∨ L) ∧ (M ∨ N) = 1 где K, L, M, N – ло­ги­че­ские пе­ре­мен­ные? В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний K, L, M и N, при ко­то­рых вы­пол­не­но дан­ное ра­вен­ство. В ка­че­стве от­ве­та вам нужно ука­зать толь­ко ко­ли­че­ство таких на­бо­ров.

За­да­ние 24 Тре­бо­ва­лось на­пи­сать про­грам­му, при вы­пол­не­нии ко­то­рой с кла­ви­а­ту­ры счи­ты­ва­ют­ся ко­ор­ди­на­ты точки на плос­ко­сти (x, y – дей­стви­тель­ные числа) и опре­де­ля­ет­ся при­над­леж­ность этой точки за­дан­ной за­кра­шен­ным об­ла­стям (вклю­чая гра­ни­цы). Про­грам­мист то­ро­пил­ся и на­пи­сал про­грам­му не­пра­виль­но.

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

1. Пе­ре­ри­суй­те и за­пол­ни­те таб­ли­цу, ко­то­рая по­ка­зы­ва­ет, как ра­бо­та­ет про­грам­ма при ар­гу­мен­тах, при­над­ле­жа­щих раз­лич­ным об­ла­стям (A, B, C, D, E, F,G и H). Точки, ле­жа­щие на гра­ни­цах об­ла­стей, от­дель­но не рас­смат­ри­вать. В столб­цах усло­вий ука­жи­те "да", если усло­вие вы­пол­нит­ся, "нет" если усло­вие не вы­пол­нит­ся, "—" (про­черк), если усло­вие не будет про­ве­рять­ся, «не изв.», если про­грам­ма ведет себя по-раз­но­му для раз­ных зна­че­ний, при­над­ле­жа­щих дан­ной об­ла­сти. В столб­це "Про­грам­ма вы­ве­дет" ука­жи­те, что про­грам­ма вы­ве­дет на экран. Если про­грам­ма ни­че­го не вы­во­дит, на­пи­ши­те "—" (про­черк). Если для раз­ных зна­че­ний, при­над­ле­жа­щих об­ла­сти, будут вы­ве­де­ны раз­ные тек­сты, на­пи­ши­те «не изв». В по­след­нем столб­це ука­жи­те "да" или "нет".

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

За­да­ние 25

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

За­да­ние 26

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

        до­ба­вить в кучу один ка­мень (дей­ствие А) или

        утро­ить ко­ли­че­ство кам­ней в куче, а затем убрать из кучи 2 камня (дей­ствие Б).

На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11 или 28 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в куче было S кам­ней, 2 ≤ S ≤ 30.

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

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

1.

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

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

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

Для ука­зан­ных зна­че­ний S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.

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

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

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

Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вани.

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

За­да­ние 27

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

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

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

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

5

123

2

1000

0

10

Про­грам­ма долж­на вы­ве­сти в по­ряд­ке воз­рас­та­ния но­ме­ра сиг­на­лов, ко­то­рые при­над­ле­жат ос­нов­но­му под­мно­же­ству дан­но­го участ­ка. Ну­ме­ра­ция эле­мен­тов по­сле­до­ва­тель­но­сти ведётся с еди­ни­цы. При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных: 2 3 5.

Ответы к заданиям 1 - 23

Ответы к заданиям 24 - 27

Задание 24

Задание 25

Вве­дем це­ло­чис­лен­ные пе­ре­мен­ные MaxEv и MaxOdd, в ко­то­рые будем за­но­сить со­от­вет­ствен­но зна­че­ния мак­си­маль­но­го чет­но­го и мак­си­маль­но­го не­чет­но­го эле­мен­та в про­смот­рен­ной части мас­си­ва и при­сво­им им на­чаль­ное зна­че­ние 0. В цикле до конца мас­си­ва: про­ве­ря­ем, яв­ля­ет­ся ли оче­ред­ной эле­мент чет­ным. Если да, то срав­ни­ва­ем его с MaxEv, если он боль­ше, за­но­сим его зна­че­ние в пе­ре­мен­ную MaxEv. Если же эле­мент не­че­тен, то срав­ни­ва­ем его с MaxOdd, если он боль­ше, за­но­сим его зна­че­ние в пе­ре­мен­ную MaxOdd. По окон­ча­нии цикла вы­во­дим раз­ность MaxEv-MaxOdd. Для опре­де­ле­ния чет­но­сти зна­че­ния эле­мен­та мас­си­ва можно вос­поль­зо­вать­ся либо стан­дарт­ной функ­ци­ей (if not odd (a[I]) then...), либо опе­ра­ци­ей опре­де­ле­ния остат­ка от де­ле­ния Ha 2(if а [ I ] mod 2 = 0 then...), либо, как при­ве­де­но в про­грам­ме ниже, опе­ра­ци­ей це­ло­чис­лен­но­го де­ле­ния. При­мер пра­виль­ной и эф­фек­тив­ной про­грам­мы (на ос­но­ве ал­го­рит­ма, ис­поль­зу­ю­ще­го од­но­крат­ный про­ход по мас­си­ву):

Задание 26

1. а) Петя может вы­иг­рать, если S =11, …, 30. При мень­ших зна­че­ни­ях S за один ход нель­зя по­лу­чить кучу, в ко­то­рой не менее 31 камня. Пете до­ста­точ­но уве­ли­чить ко­ли­че­ство кам­ней в 3 раза и от­нять два камня (дей­ствие Б).

б) Ваня может вы­иг­рать пер­вым ходом (как бы ни играл Петя), если ис­ход­но в куче будет S = 10 кам­ней. Тогда после пер­во­го хода Пети в куче будет 11 кам­ней или 28 кам­ней. В обоих слу­ча­ях Ваня вы­пол­ня­ет дей­ствие Б и вы­иг­ры­ва­ет в один ход.

2. Воз­мож­ные зна­че­ния S: 4, 9. В этих слу­ча­ях Петя, оче­вид­но, не может вы­иг­рать пер­вым ходом. Од­на­ко он может по­лу­чить кучу из 10 кам­ней (при S = 4 он вы­пол­ня­ет дей­ствие Б; при S = 9 – до­бав­ля­ет 1 ка­мень т. к. вы­пол­ня­ет дей­ствие А). Эта по­зи­ция разо­бра­на в п. 1 б. В ней игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­рать не может, а его про­тив­ник (то есть Петя) сле­ду­ю­щим ходом вы­иг­ра­ет.

3. Воз­мож­ное зна­че­ние S: 8. После пер­во­го хода Пети в куче будет 9 кам­ней или 22 камня. Если в куче ста­нет 22 камня, Ваня вы­пол­нит дей­ствие Б и вы­иг­ра­ет своим пер­вым ходом. Си­ту­а­ция, когда в куче 9 кам­ней, разо­бра­на

в п. 2. В этой си­ту­а­ции игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­ры­ва­ет своим вто­рым ходом.

В таб­ли­це изоб­ра­же­но де­ре­во воз­мож­ных пар­тий при опи­сан­ной стра­те­гии Вани. За­клю­чи­тель­ные по­зи­ции (в них вы­иг­ры­ва­ет Ваня) подчёрк­ну­ты. На ри­сун­ке это же де­ре­во изоб­ра­же­но в гра­фи­че­ском виде (оба спо­со­ба изоб­ра­же­ния де­ре­ва до­пу­сти­мы).

Задание 27 Ос­нов­ное под­мно­же­ство со­сто­ит из всех зна­че­ний сиг­на­лов, кроме 0, если он встре­ча­ет­ся, и кроме ми­ни­маль­но­го нечётного зна­че­ния, если таких зна­че­ний нечётное число. Про­грам­ма чи­та­ет все вход­ные дан­ные один раз, не за­по­ми­ная все вход­ные дан­ные в мас­си­ве, раз­мер ко­то­ро­го равен N. Во время чте­ния дан­ных за­по­ми­на­ет­ся номер 0, если он встре­тит­ся (по усло­вию все зна­че­ния раз­лич­ны, по­это­му 0 встре­ча­ет­ся не боль­ше од­но­го раза), под­счи­ты­ва­ет­ся ко­ли­че­ство нечётных зна­че­ний и ищет­ся ми­ни­маль­ное нечётное зна­че­ние. После окон­ча­ния ввода рас­пе­ча­ты­ва­ют­ся все но­ме­ра, кроме но­ме­ра 0 и но­ме­ра ми­ни­маль­но­го нечётного зна­че­ния, но толь­ко в слу­чае, если их ко­ли­че­ство нечётно. Баллы на­чис­ля­ют­ся толь­ко за про­грам­му, ко­то­рая ре­ша­ет за­да­чу хотя бы для од­но­го част­но­го слу­чая. Ниже при­ве­де­ны при­ме­ры ре­ше­ния за­да­ния на язы­ках Пас­каль и Бей­сик. До­пус­ка­ют­ся ре­ше­ния, за­пи­сан­ные на дру­гих язы­ках про­грам­ми­ро­ва­ния.