Сколь­ко зна­ча­щих цифр со­дер­жит дво­ич­ная за­пись де­ся­тич­но­го числа 16?

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

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

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

Каким из при­ведённых ниже вы­ра­же­ний может быть F?

1)  x1 ∧ ¬x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ x6 ∧ x7

2)  x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7

3)  ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7

4)  ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7

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

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

Сим­вол «*» (звёздоч­ка) озна­ча­ет любую по­сле­до­ва­тель­ность сим­во­лов

про­из­воль­ной длины, в том числе «*» может за­да­вать и пу­стую по­сле­до­ва­тель­ность.

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

ban?*.?xt

1)  ban.txt

2)  banan.xt

3)  bank.xt

4)  bank.txt

Рас­смот­рим ал­го­ритм, пре­об­ра­зу­ю­щий одно целое число в дру­гое.

A. Умно­жить те­ку­щее число на 2.

B. При­ба­вить к ре­зуль­та­ту 1.

C. Если по­лу­чив­ше­е­ся число боль­ше или равно 17, вы­честь из него 17.

Какое по­лу­чит­ся число, если по­вто­рить этот ал­го­ритм 7 раз для ис­ход­но­го числа 4?

1)  9

2)  10

3)  13

4)  4

На го­род­ской тур олим­пи­а­ды по ма­те­ма­ти­ке от­би­ра­ют­ся те уча­щи­е­ся, кто на­брал на рай­он­ном туре не менее 10 бал­лов или пол­но­стью решил хотя бы одну из двух самых слож­ных задач (№ 6 или № 7). За пол­ное ре­ше­ние

задач 1– 4 даётся 2 балла; задач 5, 6 – 3 балла; за­да­чи 7 – 4 балла. Дан фраг­мент таб­ли­цы ре­зуль­та­тов рай­он­но­го тура.

Сколь­ко де­во­чек из этой таб­ли­цы про­шли на го­род­ской тур?

В элек­трон­ной таб­ли­це зна­че­ние фор­му­лы =СРЗНАЧ(B5:E5) равно 100. Чему равно зна­че­ние фор­му­лы =СУММ(B5:D5), если зна­че­ние ячей­ки E5 равно 50? Пу­стых ячеек в таб­ли­це нет.

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

1)  22

2)  44

3)  87

4)  174

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся не­рав­но­мер­ный (по длине) код: А – 0; Б – 100; В – 101. Каким ко­до­вым сло­вом нужно ко­ди­ро­вать сим­вол Г, чтобы длина его была ми­ни­маль­ной, а код при этом до­пус­кал од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на сим­во­лы?

1)  1

2)  11

3)  01

4)  010

На чис­ло­вой пря­мой даны два от­рез­ка: P = [12, 62] и Q = [32, 92].

Вы­бе­ри­те такой от­ре­зок A, что фор­му­ла

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

1)  [5, 60]

2)  [10, 80]

3)  [40, 100]

4)  [70, 120]

Для ре­ги­стра­ции на сайте не­ко­то­рой стра­ны поль­зо­ва­те­лю тре­бу­ет­ся при­ду­мать па­роль. Длина па­ро­ля  — ровно 7 сим­во­лов. В ка­че­стве сим­во­лов ис­поль­зу­ют­ся де­ся­тич­ные цифры и 30 раз­лич­ных букв мест­но­го ал­фа­ви­та, причём все буквы ис­поль­зу­ют­ся в двух на­чер­та­ни­ях: как строч­ные, так и про­пис­ные (ре­гистр буквы имеет зна­че­ние!). Под хра­не­ние каж­до­го та­ко­го па­ро­ля на ком­пью­те­ре от­во­дит­ся ми­ни­маль­но воз­мож­ное и оди­на­ко­вое целое ко­ли­че­ство бай­тов, при этом ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством битов. Опре­де­ли­те объём па­мя­ти, ко­то­рый за­ни­ма­ет хра­не­ние 40 па­ро­лей. (Ответ дайте в бай­тах.)

Ниже при­ведён фраг­мент про­грам­мы, за­пи­сан­ный на пяти язы­ках про­грам­ми­ро­ва­ния.

Мас­сив A дву­мер­ный; в про­грам­ме рас­смат­ри­ва­ет­ся его фраг­мент, со­от­вет­ству­ю­щий зна­че­ни­ям каж­до­го ин­дек­са от 1 до 9.

Сколь­ко эле­мен­тов ука­зан­но­го фраг­мен­та мас­си­ва A будут при­ни­мать нечётные зна­че­ния после вы­пол­не­ния дан­но­го фраг­мен­та про­грам­мы?

Си­сте­ма ко­манд ис­пол­ни­те­ля РОБОТ, «жи­ву­ще­го» в клет­ках пря­мо­уголь­но­го ла­би­рин­та на плос­ко­сти:

вверх, вниз, влево, впра­во.

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

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

В цикле

ПОКА <усло­вие> ко­ман­да

ко­ман­да вы­пол­ня­ет­ся, пока усло­вие ис­тин­но, иначе про­ис­хо­дит пе­ре­ход на сле­ду­ю­щую стро­ку про­грам­мы.

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

НА­ЧА­ЛО

ПОКА < снизу сво­бод­но > влево

ПОКА < слева сво­бод­но > вверх

ПОКА < свер­ху сво­бод­но > впра­во

ПОКА < спра­ва сво­бод­но > вниз

КОНЕЦ

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

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

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

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 1, вто­рая удва­и­ва­ет его.

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

умножь на 2

при­бавь 1

умножь на 2

при­бавь 1,

ко­то­рая пре­об­ра­зу­ет число 1 в число 7.

За­пи­ши­те по­ря­док ко­манд в про­грам­ме пре­об­ра­зо­ва­ния числа 4 в число 94, со­дер­жа­щей не более 8 ко­манд, ука­зы­вая лишь но­ме­ра ко­манд. Если таких про­грамм более одной, то за­пи­ши­те любую из них.

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

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

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

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

Все 4-⁠бук­вен­ные слова, со­став­лен­ные из букв В, Н, Р, Т, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке и про­ну­ме­ро­ва­ны.

Вот на­ча­ло спис­ка:

1.  ВВВВ

2.  ВВВН

3.  ВВВР

4.  ВВВТ

5.  ВВНВ

...

За­пи­ши­те слово, ко­то­рое стоит под но­ме­ром 250.

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

Для Ва­ше­го удоб­ства про­грам­ма пред­став­ле­на на четырёх язы­ках про­грам­ми­ро­ва­ния.

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

F(n)  =  2 при n  =  1;

F(n)  =  F(n – 1) · n при n ≥ 2.

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

За­пи­ши­те число 83 в тро­ич­ной си­сте­ме счис­ле­ния. В от­ве­те ука­жи­те толь­ко цифры, ос­но­ва­ние си­сте­мы счис­ле­ния пи­сать не нужно.

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

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

Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Л?

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

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

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

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

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

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

· время, тре­бу­е­мое на сжа­тие до­ку­мен­та,  — 10 се­кунд; на рас­па­ков­ку  — 1 се­кун­да?

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

На­при­мер, за­пись от­ве­та Б23 озна­ча­ет, что спо­соб Б быст­рее на 23 се­кун­ды.

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

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

Маска: 255.255.192.0

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

При­мер.

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

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

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

В таб­ли­це при­ве­де­ны за­про­сы и ко­ли­че­ство най­ден­ных по ним стра­ниц не­ко­то­ро­го сег­мен­та сети Ин­тер­нет.

Какое ко­ли­че­ство стра­ниц (в ты­ся­чах) будет най­де­но по за­про­су Лин­кор?

Счи­та­ет­ся, что все за­про­сы вы­пол­ня­лись прак­ти­че­ски од­но­вре­мен­но, так что набор стра­ниц, со­дер­жа­щих все ис­ко­мые слова, не из­ме­нял­ся за время вы­пол­не­ния за­про­сов.

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

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

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

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 1, вто­рая при­бав­ля­ет к числу на экра­не 10.

Про­грам­ма для При­ба­ви­те­ля  — это по­сле­до­ва­тель­ность ко­манд.

Сколь­ко есть про­грамм, ко­то­рые число 10 пре­об­ра­зу­ют в число 31?

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

Сколь­ко раз­лич­ных ре­ше­ний имеет си­сте­ма урав­не­ний

¬x1 ∨ x2 = 1

¬x2 ∨ x3 = 1

…

¬x9 ∨ x10 = 1,

где x1, x2, … x10  — ло­ги­че­ские пе­ре­мен­ные?

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

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

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

1.  Пе­ре­ри­суй­те и за­пол­ни­те таб­ли­цу, ко­то­рая по­ка­зы­ва­ет, как ра­бо­та­ет про­грам­ма при ар­гу­мен­тах, при­над­ле­жа­щих раз­лич­ным об­ла­стям (A, B, C, D и E). Гра­ни­цы (точки –1, 5, 11 и 17) при­над­ле­жат за­штри­хо­ван­ным об­ла­стям (B и D со­от­вет­ствен­но).

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

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

Дан це­ло­чис­лен­ный мас­сив из 30 эле­мен­тов. Эле­мен­ты мас­си­ва могут при­ни­мать зна­че­ния от −20 до 20  — све­де­ния о тем­пе­ра­ту­ре за каж­дый день но­яб­ря. Опи­ши­те на рус­ском языке или на одном из язы­ков про­грам­ми­ро­ва­ния ал­го­ритм, ко­то­рый поз­во­ля­ет под­счи­тать и вы­ве­сти сред­нюю тем­пе­ра­ту­ру среди дней, когда были за­мо­роз­ки (тем­пе­ра­ту­ра опус­ка­лась ниже 0 °C). Га­ран­ти­ру­ет­ся, что хотя бы в один день но­яб­ря была от­ри­ца­тель­ная тем­пе­ра­ту­ра.

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

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

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

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

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

В на­чаль­ный мо­мент в куче было S кам­ней; 1 ≤ S ≤ 101.

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

встре­тить­ся при раз­лич­ной игре про­тив­ни­ка.

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

За­да­ние 1

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

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

За­да­ние 2

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

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

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

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

За­да­ние 3

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

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

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

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

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

Му­ни­ци­паль­ный этап олим­пи­а­ды по ин­фор­ма­ти­ке про­во­дил­ся для уче­ни­ков 7–11-х клас­сов. Все уче­ни­ки участ­во­ва­ли в общем кон­кур­се. Каж­дый участ­ник олим­пи­а­ды мог на­брать от 0 до 400 бал­лов. По по­ло­же­нию об олим­пиа­де по­бе­ди­те­лем приз­наётся участ­ник, на­брав­ший наи­боль­шее ко­ли­че­ство бал­лов, при усло­вии, что им на­бра­но боль­ше по­ло­ви­ны воз­мож­ных бал­лов. По­бе­ди­те­лей может быть не­сколь­ко, если это ко­ли­че­ство бал­лов на­бе­рут не­сколь­ко че­ло­век; а может и не быть со­всем, если никто не наберёт боль­ше по­ло­ви­ны.

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

В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся ре­зуль­тат од­но­го из участ­ни­ков олим­пи­а­ды в сле­ду­ю­щем фор­ма­те:

<Фа­ми­лия> <Имя> <класс> <баллы>,

где <Фа­ми­лия>  — стро­ка, со­сто­я­щая не более чем из 20 не­про­бель­ных сим­во­лов; <Имя>  — стро­ка, со­сто­я­щая не более чем из 15 не­про­бель­ных сим­во­лов; <класс>  — число от 7 до 11; <баллы>  — целое число от 0 до 400 на­бран­ных участ­ни­ком бал­лов. <Фа­ми­лия> и <Имя>, <Имя> и <класс>, а также <класс> и <баллы> раз­де­ле­ны одним про­бе­лом.

При­мер вход­ной стро­ки:

Ива­нов Пётр 10 275

Про­грам­ма долж­на вы­во­дить через про­бел Фа­ми­лию и Имя ис­ко­мо­го участ­ни­ка или их число. При­мер вы­ход­ных дан­ных:

Куз­не­цов Иван

Вто­рой ва­ри­ант вы­ход­ных дан­ных:

4