На ри­сун­ке схема дорог изоб­ра­же­на в виде графа, в таб­ли­це звёздоч­кой от­ме­че­но на­ли­чие до­ро­ги между двумя населёнными пунк­та­ми. Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, ну­ме­ра­ция пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Кроме того, при за­пол­не­нии таб­ли­цы одну до­ро­гу слу­чай­но про­пу­сти­ли. Опре­де­ли­те два населённых пунк­та, до­ро­га между ко­то­ры­ми есть на графе, но не от­ме­че­на в таб­ли­це. В от­ве­те за­пи­ши­те но­ме­ра этих пунк­тов в таб­ли­це в по­ряд­ке воз­рас­та­ния, без раз­де­ли­те­лей между ними, как дву­знач­ное число. На­при­мер, если бы в таб­ли­це была про­пу­ще­на до­ро­га между пунк­та­ми П1 и П2, в от­ве­те сле­до­ва­ло бы на­пи­сать число 12.

Ло­ги­че­ская функ­ция F задаётся вы­ра­же­ни­ем:

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

Опре­де­ли­те, ка­ко­му столб­цу таб­ли­цы ис­тин­но­сти со­от­вет­ству­ет каж­дая из пе­ре­мен­ных w, x, y, z.

В от­ве­те на­пи­ши­те буквы w, x, y, z в том по­ряд­ке, в ко­то­ром идут со­от­вет­ству­ю­щие им столб­цы (сна­ча­ла буква, со­от­вет­ству­ю­щая пер­во­му столб­цу; затем буква, со­от­вет­ству­ю­щая вто­ро­му столб­цу, и т. д.). Буквы в от­ве­те пи­ши­те под­ряд, ни­ка­ких раз­де­ли­те­лей между бук­ва­ми ста­вить не нужно.

При­мер. Пусть за­да­ны вы­ра­же­ние x → y, за­ви­ся­щее от двух пе­ре­мен­ных x и y, и фраг­мент таб­ли­цы ис­тин­но­сти.

Тогда пер­во­му столб­цу со­от­вет­ству­ет пе­ре­мен­ная y, а вто­ро­му столб­цу со­от­вет­ству­ет пе­ре­мен­ная x. В от­ве­те нужно на­пи­сать: yx.

В файле при­ведён фраг­мент базы дан­ных «Про­дук­ты», со­дер­жа­щей ин­фор­ма­цию о по­став­ках то­ва­ров и их про­да­же. База дан­ных со­сто­ит из трёх таб­лиц.

Таб­ли­ца «Тор­гов­ля» со­дер­жит за­пи­си о по­став­ках и про­да­жах то­ва­ров в ма­га­зи­нах го­ро­да в июне 2021 г. Таб­ли­ца «Товар» со­дер­жит дан­ные о то­ва­рах. Таб­ли­ца «Ма­га­зин» со­дер­жит дан­ные о ма­га­зи­нах.

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

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

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

Все за­глав­ные буквы рус­ско­го ал­фа­ви­та за­ко­ди­ро­ва­ны не­рав­но­мер­ным дво­ич­ным кодом, в ко­то­ром ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это усло­вие обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний. Из­вест­но, что слово ПОТОП ко­ди­ру­ет­ся как 00010011100000. Какой код со­от­вет­ству­ет букве Т?

Ал­го­ритм по­лу­ча­ет на вход на­ту­раль­ное число N и стро­ит по нему новое число R сле­ду­ю­щим об­ра­зом.

1.  Стро­ит­ся дво­ич­ная за­пись числа N.

2.  Если число N чётное, то к дво­ич­ной за­пи­си слева до­пи­сы­ва­ют­ся цифры 11.

В про­тив­ном слу­чае (число N нечётное) к дво­ич­ной за­пи­си слева до­пи­сы­ва­ет­ся цифра 1, а спра­ва  — цифры 10.

3.  Ре­зуль­та­том ра­бо­ты ал­го­рит­ма ста­но­вит­ся де­ся­тич­ная за­пись по­лу­чен­но­го числа R.

При­мер.  Дано число N  =  13. Ал­го­ритм ра­бо­та­ет сле­ду­ю­щим об­ра­зом.

1.  Стро­им дво­ич­ную за­пись: 13₁₀  =  1101₂.

2.  Число 13 нечётно. До­пи­сы­ва­ем 1 слева и 10 спра­ва, по­лу­ча­ем 1110110₂  =  118₁₀.

3.  Ре­зуль­тат ра­бо­ты ал­го­рит­ма R  =  118.

Ука­жи­те мак­си­маль­ное число R, ко­то­рое может быть ре­зуль­та­том ра­бо­ты дан­но­го ал­го­рит­ма, при усло­вии, что N при­над­ле­жит от­рез­ку [234 567 890; 567 891 234].

Ис­пол­ни­тель Че­ре­па­ха дей­ству­ет на плос­ко­сти с де­кар­то­вой си­сте­мой ко­ор­ди­нат. В на­чаль­ный мо­мент Че­ре­па­ха на­хо­дит­ся в на­ча­ле ко­ор­ди­нат, её го­ло­ва на­прав­ле­на вдоль по­ло­жи­тель­но­го на­прав­ле­ния оси ор­ди­нат, хвост опу­щен. При опу­щен­ном хво­сте Че­ре­па­ха остав­ля­ет на поле след в виде линии. В каж­дый кон­крет­ный мо­мент из­вест­но по­ло­же­ние ис­пол­ни­те­ля и на­прав­ле­ние его дви­же­ния. У ис­пол­ни­те­ля су­ще­ству­ет две ко­ман­ды: Вперёд r (где r  — ра­ци­о­наль­ное число), вы­зы­ва­ю­щая пе­ре­дви­же­ние Че­ре­па­хи на рас­сто­я­ние, рав­ное r, в том на­прав­ле­нии, куда ука­зы­ва­ет её го­ло­ва; На­пра­во m (где m  — целое число), вы­зы­ва­ю­щая из­ме­не­ние на­прав­ле­ния дви­же­ния на m гра­ду­сов по ча­со­вой стрел­ке.

За­пись По­вто­ри k [Ко­ман­да 1 Ко­ман­да 2 ... Ко­ман­да S] озна­ча­ет, что по­сле­до­ва­тель­ность из S ко­манд по­вто­рит­ся k раз.

Че­ре­па­хе был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм:

На­пра­во 60 По­вто­ри 2 [Вперёд 10 На­пра­во 120 Вперёд 5 На­пра­во 240] На­пра­во 120 Вперёд 3 На­пра­во 90 Вперёд На­пра­во 90 Вперёд 8 На­пра­во 120 По­вто­ри 2 [Вперёд 10 На­ле­во 120 Вперёд 5 На­ле­во 240].

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

Ви­та­лий де­ла­ет сним­ки ин­те­рес­ных мест и со­бы­тий циф­ро­вой ка­ме­рой сво­е­го смарт­фо­на. Каж­дая фо­то­гра­фия

пред­став­ля­ет собой раст­ро­вое изоб­ра­же­ние раз­ме­ром 1024 × 768 пик­се­лей и с па­лит­рой из 2²³ цве­тов. В конце дня Ви­та­лий от­прав­ля­ет сним­ки дру­зьям с по­мо­щью при­ло­же­ния-мес­сен­дже­ра. Для эко­но­мии тра­фи­ка при­ло­же­ние сжи­ма­ет сним­ки, ис­поль­зуя раз­мер 800 × 600 пик­се­лей и глу­би­ну цвета 22 бита. Сколь­ко Кбайт тра­фи­ка эко­но­мит­ся таким об­ра­зом при пе­ре­да­че 100 фо­то­гра­фий?

В от­ве­те ука­жи­те целую часть по­лу­чен­но­го числа.

Все ше­сти­бук­вен­ные слова, со­став­лен­ные из букв К, Л, Н, Т, Э, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке и про­ну­ме­ро­ва­ны, на­чи­ная с 1. На­ча­ло спис­ка вы­гля­дит так:

1.  КККККК

2.  КККККЛ

3.  КККККН

4.  КККККТ

5.  КККККЭ

...

Под каким но­ме­ром в спис­ке идёт слово ККЛКЛК?

От­крой­те файл элек­трон­ной таб­ли­цы, со­дер­жа­щей в каж­дой стро­ке шесть на­ту­раль­ных чисел. Опре­де­ли­те ко­ли­че­ство строк таб­ли­цы, со­дер­жа­щих числа, для ко­то­рых вы­пол­не­ны оба усло­вия:

—  в стро­ке есть толь­ко два рав­ных числа, осталь­ные 4 раз­лич­ны;

—  сред­нее ариф­ме­ти­че­ское по­вто­ря­ю­щих­ся чисел мень­ше, чем сред­нее ариф­ме­ти­че­ское осталь­ных чисел стро­ки.

В от­ве­те за­пи­ши­те толь­ко число.

По­весть бра­тьев Стру­гац­ких «По­не­дель­ник на­чи­на­ет­ся в суб­бо­ту» со­сто­ит из трёх ис­то­рий. Опре­де­ли­те, сколь­ко раз в тре­тьей ис­то­рии, вклю­чая за­го­лов­ки, эпи­гра­фы и снос­ки, встре­ча­ют­ся слова, на­чи­на­ю­щи­е­ся c буквы Я (за­глав­ной или строч­ной) и со­дер­жа­щие не менее трёх букв. В этом за­да­нии части слова, раз­делённые де­фи­сом, рас­смат­ри­ва­ют­ся как от­дель­ные слова.

На­при­мер, слово «кто-⁠то» учи­ты­ва­ет­ся как два от­дель­ных слова: трёхбук­вен­ное и двух­бук­вен­ное.

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 15 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы из 12-⁠сим­воль­но­го на­бо­ра: А, В, C, D, Е, F, G, H, K, L, M, N. В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Кроме соб­ствен­но па­ро­ля, для каж­до­го поль­зо­ва­те­ля в си­сте­ме хра­нят­ся до­пол­ни­тель­ные све­де­ния, для чего вы­де­ле­но целое число байт; это число одно и то же для всех поль­зо­ва­те­лей. Для хра­не­ния све­де­ний о 20 поль­зо­ва­те­лях по­тре­бо­ва­лось 400 байт. Сколь­ко байт вы­де­ле­но для хра­не­ния до­пол­ни­тель­ных све­де­ний об одном поль­зо­ва­те­ле? В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство байт.

Ис­пол­ни­тель МТ пред­став­ля­ет собой чи­та­ю­щую и за­пи­сы­ва­ю­щую го­лов­ку, ко­то­рая может пе­ре­дви­гать­ся вдоль бес­ко­неч­ной го­ри­зон­таль­ной ленты, раз­делённой на рав­ные ячей­ки. В каж­дой ячей­ке на­хо­дит­ся ровно один сим­вол из ал­фа­ви­та ис­пол­ни­те­ля (мно­же­ство сим­во­лов A  =  {a₀, a₁, ..., a_n − 1}), вклю­чая спе­ци­аль­ный пу­стой сим­вол a₀.

Время ра­бо­ты ис­пол­ни­те­ля де­лит­ся на дис­крет­ные такты (шаги). На каж­дом такте го­лов­ка МТ на­хо­дит­ся в одном из мно­же­ства до­пу­сти­мых со­сто­я­ний Q  =  {q₀, q₁, ..., q_n − 1}. В на­чаль­ный мо­мент вре­ме­ни го­лов­ка на­хо­дит­ся в на­чаль­ном со­сто­я­нии q₀.

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

Про­грам­ма ра­бо­ты ис­пол­ни­те­ля МТ задаётся в таб­лич­ном виде.

В пер­вой стро­ке пе­ре­чис­ле­ны все воз­мож­ные сим­во­лы в те­ку­щей ячей­ке ленты, в пер­вом столб­це  — воз­мож­ные со­сто­я­ния го­лов­ки. На пе­ре­се­че­нии i⁠-й стро­ки и j⁠-го столб­ца на­хо­дит­ся ко­ман­да, ко­то­рую вы­пол­ня­ет МТ, когда го­лов­ка обо­зре­ва­ет j⁠-й сим­вол, на­хо­дясь в i⁠-м со­сто­я­нии. Если пара «сим­вол  — со­сто­я­ние» не­воз­мож­на, то клет­ка для ко­ман­ды остаётся пу­стой.

Каж­дая ко­ман­да со­сто­ит из трёх эле­мен­тов, раз­делённых за­пя­ты­ми: пер­вый эле­мент  — за­пи­сы­ва­е­мый в те­ку­щую ячей­ку сим­вол ал­фа­ви­та (может сов­па­дать с тем, ко­то­рый там уже за­пи­сан). Вто­рой эле­мент  — один из четырёх сим­во­лов «L», «R», «N», «S». Сим­во­лы «L» и «R» озна­ча­ют сдвиг в левую или пра­вую ячей­ки со­от­вет­ствен­но, «N»  — от­сут­ствие сдви­га, «S»  — за­вер­ше­ние ра­бо­ты ис­пол­ни­те­ля МТ после вы­пол­не­ния те­ку­щей ко­ман­ды.

Сдвиг про­ис­хо­дит после за­пи­си сим­во­ла в те­ку­щую ячей­ку. Тре­тий эле­мент  — новое со­сто­я­ние го­лов­ки после вы­пол­не­ния ко­ман­ды.

На­при­мер, ко­ман­да 0, L, q3 вы­пол­ня­ет­ся сле­ду­ю­щим об­ра­зом: в те­ку­щую ячей­ку за­пи­сы­ва­ет­ся сим­вол «0», затем го­лов­ка сдви­га­ет­ся в со­сед­нюю слева ячей­ку и пе­ре­хо­дит в со­сто­я­ние q3.

При­ведём при­мер вы­пол­не­ния про­грам­мы, за­дан­ной таб­лич­но. На ленте за­пи­са­но не­из­вест­ное не­ну­ле­вое ко­ли­че­ство рас­по­ло­жен­ных под­ряд в со­сед­них ячей­ках сим­во­лов «Z», все осталь­ные ячей­ки ленты за­пол­не­ны пу­стым сим­во­лом «λ». В на­чаль­ный мо­мент вре­ме­ни го­лов­ка на­хо­дит­ся на не­из­вест­ном не­ну­ле­вом рас­сто­я­нии спра­ва от са­мо­го пра­во­го сим­во­ла «Z».

Про­грам­ма.

за­ме­ня­ет на ленте все сим­во­лы «Z» на «X» и оста­нав­ли­ва­ет ис­пол­ни­те­ля в пер­вой ячей­ке слева от по­сле­до­ва­тель­но­сти сим­во­лов «X».

Воз­мож­ное на­чаль­ное со­сто­я­ние ис­пол­ни­те­ля.

...

λ

λ

Z

Z

Z

Z

λ

...

Ко­неч­но со­сто­я­ние ис­пол­ни­те­ля после за­вер­ше­ния вы­пол­не­ния про­грам­мы.

...

λ

X

X

X

X

λ

λ

...

Вы­пол­ни­те за­да­ние.

На ленте в со­сед­них ячей­ках за­пи­са­на по­сле­до­ва­тель­ность из 1100 сим­во­лов, вклю­ча­ю­щая толь­ко нули, еди­ни­цы и двой­ки. Ячей­ки спра­ва и слева от по­сле­до­ва­тель­но­сти за­пол­не­ны пу­сты­ми сим­во­ла­ми «λ». В на­чаль­ный мо­мент вре­ме­ни го­лов­ка рас­по­ло­же­на в бли­жай­шей ячей­ке слева от по­сле­до­ва­тель­но­сти.

Про­грам­ма ра­бо­ты ис­пол­ни­те­ля.

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

В тер­ми­но­ло­гии сетей TCP/⁠IP маска сети  — это дво­ич­ное число, мень­шее 2³²; в маске сна­ча­ла (в стар­ших раз­ря­дах) стоят еди­ни­цы, а затем с не­ко­то­ро­го места нули. Маска опре­де­ля­ет, какая часть IP-⁠ад­ре­са узла сети от­но­сит­ся к ад­ре­су сети, а какая  — к ад­ре­су са­мо­го узла в этой сети. Обыч­но маска за­пи­сы­ва­ет­ся по тем же пра­ви­лам, что и IP-⁠адрес,  — в виде четырёх байт, причём каж­дый байт за­пи­сы­ва­ет­ся в виде де­ся­тич­но­го числа. Адрес сети по­лу­ча­ет­ся в ре­зуль­та­те при­ме­не­ния по­раз­ряд­ной конъ­юнк­ции к за­дан­но­му IP-⁠ад­ре­су узла и маске.

На­при­мер, если IP-⁠адрес узла равен 131.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 131.32.240.0.

Для узла с IP-⁠ад­ре­сом 84.77.95.123 тре­тий слева байт маски равен 224. Чему равен тре­тий байт ад­ре­са сети для этого узла?

Опе­ран­ды ариф­ме­ти­че­ско­го вы­ра­же­ния за­пи­са­ны в си­сте­ме счис­ле­ния с ос­но­ва­ни­я­ми 13 и 18:

В за­пи­си чисел пе­ре­мен­ной x обо­зна­че­на не­из­вест­ная цифра из ал­фа­ви­та де­ся­тич­ной си­сте­мы счис­ле­ния. Опре­де­ли­те наи­мень­шее зна­че­ние x, при ко­то­ром зна­че­ние дан­но­го ариф­ме­ти­че­ско­го вы­ра­же­ния крат­но 184. Для най­ден­но­го зна­че­ния x вы­чис­ли­те част­ное от де­ле­ния зна­че­ния ариф­ме­ти­че­ско­го вы­ра­же­ния на 184 и ука­жи­те его в от­ве­те в де­ся­тич­ной си­сте­ме счис­ле­ния. Ос­но­ва­ние си­сте­мы счис­ле­ния в от­ве­те ука­зы­вать не нужно.

Обо­зна­чим через m&n по­раз­ряд­ную конъ­юнк­цию не­от­ри­ца­тель­ных целых чисел m и n. На­при­мер, 14&5  =  1110₂&0101₂  =  0100₂  =  4. Для ка­ко­го наи­мень­ше­го не­от­ри­ца­тель­но­го це­ло­го числа А фор­му­ла

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

F(n)  =  n, если n > 1 000 000;

F(n)  =  n + F(2n), если n ≤ 1 000 000;

Сколь­ко су­ще­ству­ет таких на­ту­раль­ных чисел n (вклю­чая число 1000), для ко­то­рых G(n)  =  G(1000)?

Файл со­дер­жит по­сле­до­ва­тель­ность на­ту­раль­ных чисел, не пре­вы­ша­ю­щих 100 000. Назовём трой­кой три иду­щих под­ряд эле­мен­та по­сле­до­ва­тель­но­сти.

Опре­де­ли­те ко­ли­че­ство троек, для ко­то­рых вы­пол­ня­ют­ся сле­ду­ю­щие усло­вия:

—  в трой­ке не более од­но­го пя­ти­знач­но­го числа;

—  в трой­ке есть число, по­след­няя цифра ко­то­ро­го сов­па­да­ет с по­след­ней циф­рой ми­ни­маль­но­го эле­мен­та всей по­сле­до­ва­тель­но­сти;

—  в трой­ке нет чисел, по­след­няя цифра ко­то­рых сов­па­да­ет с по­след­ней циф­рой мак­си­маль­но­го эле­мен­та всей по­сле­до­ва­тель­но­сти.

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

Ответ:

Робот стоит в левом верх­нем углу пря­мо­уголь­но­го поля, в каж­дой клет­ке ко­то­ро­го за­пи­са­но целое число. В не­ко­то­рых клет­ках за­пи­са­но число –1, в эти клет­ки ро­бо­ту за­хо­дить нель­зя. Для ва­ше­го удоб­ства такие клет­ки вы­де­ле­ны

тёмным фоном. В осталь­ных клет­ках за­пи­са­ны по­ло­жи­тель­ные числа. За один ход робот может пе­ре­ме­стить­ся на одну клет­ку впра­во или на одну клет­ку вниз.

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

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

За­да­ние 2. Опре­де­ли­те общее ко­ли­че­ство кле­ток поля, вклю­чая стар­то­вую, в ко­то­рые может по­пасть робот.

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це. В от­ве­те за­пи­ши­те два числа: сна­ча­ла ответ на за­да­ние 1, затем ответ на за­да­ние 2.

Ответ:

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

На­при­мер, если в куче 5 кам­ней, то за один ход можно по­лу­чить 6 или 10 кам­ней, а если в куче 6 кам­ней, то за один ход можно по­лу­чить 7 или 9 кам­ней.

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

В на­ча­ле игры в куче было S кам­ней, 1 ≤ S ≤ 107.

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

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

В от­ве­те за­пи­ши­те най­ден­ные зна­че­ния в по­ряд­ке воз­рас­та­ния.

Ответ:

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

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

Ин­фор­ма­ция о про­цес­сах пред­став­ле­на в файле в виде таб­ли­цы. В пер­вой стро­ке таб­ли­цы ука­зан иден­ти­фи­ка­тор про­цес­са (ID), во вто­рой стро­ке таб­ли­цы  — время его вы­пол­не­ния в мил­ли­се­кун­дах, в тре­тьей стро­ке пе­ре­чис­ле­ны с раз­де­ли­те­лем «;» ID про­цес­сов, от ко­то­рых за­ви­сит дан­ный про­цесс. Если про­цесс яв­ля­ет­ся не­за­ви­си­мым, то в таб­ли­це ука­за­но зна­че­ние 0.

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

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных в файле:

В дан­ном слу­чае не­за­ви­си­мые про­цес­сы 1 и 2 могут вы­пол­нять­ся па­рал­лель­но, при этом про­цесс 1 за­вер­шит­ся через 4 мс, а про­цесс 2  — через 3 мс с мо­мен­та стар­та. Про­цесс 3 может на­чать­ся толь­ко после за­вер­ше­ния обоих про­цес­сов 1 и 2, то есть через 4 мс после стар­та. Он длит­ся 1 мс и за­кон­чит­ся через 4 + 1  =  5 мс после стар­та. Вы­пол­не­ние про­цес­са 4 может на­чать­ся толь­ко после за­вер­ше­ния про­цес­са 3, то есть через 5 мс. Он длит­ся 7 мс, так что ми­ни­маль­ное время за­вер­ше­ния всех про­цес­сов равно 5 + 7  =  12 мс.

Вы­пол­ни­те за­да­ния, ис­поль­зуя дан­ные из файла ниже:

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

1.  При­ба­вить 1.

2.  Умно­жить на 2.

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

Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 1 ре­зуль­та­том яв­ля­ет­ся число 35, при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 10 и не со­дер­жит 17?

Тра­ек­то­рия вы­чис­ле­ний про­грам­мы  — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 121 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 8, 16, 17.

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

Участ­ни­ки вик­то­ри­ны пись­мен­но от­ве­ча­ют на 10 во­про­сов раз­лич­ной слож­но­сти. За пра­виль­ный ответ на­чис­ля­ет­ся от 1 до 5 бал­лов в за­ви­си­мо­сти от слож­но­сти во­про­са. За не­вер­ный ответ вы­чи­та­ет­ся от 1 до 5 бал­лов. Участ­ник может не от­ве­чать на какой-то во­прос, в таком слу­чае баллы за этот во­прос не на­чис­ля­ют­ся.

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

1)  сумма  — общее ко­ли­че­ство на­бран­ных бал­лов;

2)  плюсы  — сумма бал­лов без учёта не­вер­ных от­ве­тов;

3)  от­ве­ты  — общее ко­ли­че­ство сдан­ных от­ве­тов (вер­ных и не­вер­ных).

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

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

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

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

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

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

Вход­ные дан­ные.

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N (N ≤ 10 000)  — общее ко­ли­че­ство участ­ни­ков. Каж­дая из сле­ду­ю­щих N строк со­от­вет­ству­ет од­но­му участ­ни­ку и со­дер­жит 11 целых чисел, раз­делённых про­бе­ла­ми: сна­ча­ла ID участ­ни­ка, затем  — баллы, по­лу­чен­ные им за каж­дый из 10 во­про­сов.

Га­ран­ти­ру­ет­ся, что ID участ­ни­ков не по­вто­ря­ют­ся.

В от­ве­те за­пи­ши­те два целых числа: сна­ча­ла тре­бу­е­мый ID, затем тре­бу­е­мое ко­ли­че­ство.

Ответ:

Фраг­мент звёзд­но­го неба спро­еци­ро­ван на плос­кость с де­кар­то­вой си­сте­мой ко­ор­ди­нат. Учёный решил про­ве­сти кла­сте­ри­за­цию по­лу­чен­ных точек, яв­ля­ю­щих­ся изоб­ра­же­ни­я­ми звёзд, то есть раз­бить их мно­же­ство на N не­пе­ре­се­ка­ю­щих­ся не­пу­стых под­мно­жеств (кла­сте­ров), таких, что точки каж­до­го под­мно­же­ства лежат внут­ри квад­ра­та со сто­ро­ной дли­ной H, причём эти квад­ра­ты между собой не пе­ре­се­ка­ют­ся. Сто­ро­ны квад­ра­та не обя­за­тель­но па­рал­лель­ны ко­ор­ди­нат­ным осям. Га­ран­ти­ру­ет­ся, что такое раз­би­е­ние су­ще­ству­ет и един­ствен­но для за­дан­ных раз­ме­ров квад­ра­та.

Будем на­зы­вать цен­тром кла­сте­ра точку этого кла­сте­ра, сумма рас­сто­я­ний от ко­то­рой до всех осталь­ных точек кла­сте­ра ми­ни­маль­на. Для каж­до­го кла­сте­ра га­ран­ти­ру­ет­ся един­ствен­ность его цен­тра. Рас­сто­я­ние между двумя точ­ка­ми на плос­ко­сти и вы­чис­ля­ет­ся по фор­му­ле:

В файле А хра­нят­ся ко­ор­ди­на­ты точек двух кла­сте­ров, где H  =  4,7 для каж­до­го кла­сте­ра. В каж­дой стро­ке за­пи­са­на ин­фор­ма­ция о рас­по­ло­же­нии на карте одной звез­ды: сна­ча­ла ко­ор­ди­на­та x, затем ко­ор­ди­на­та y. Из­вест­но, что ко­ли­че­ство точек не пре­вы­ша­ет 1000.

В файле Б хра­нят­ся ко­ор­ди­на­ты точек трёх кла­сте­ров, где H  =  4 для каж­до­го кла­сте­ра. Из­вест­но, что ко­ли­че­ство точек не пре­вы­ша­ет 10 000. Струк­ту­ра хра­не­ния ин­фор­ма­ции в файле Б ана­ло­гич­на файлу A.

Для каж­до­го файла опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем вы­чис­ли­те два числа: P_x  — сред­нее ариф­ме­ти­че­ское абс­цисс цен­тров кла­сте­ров и P_y  — сред­нее ариф­ме­ти­че­ское ор­ди­нат цен­тров кла­сте­ров.

В от­ве­те за­пи­ши­те че­ты­ре числа: в пер­вой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния затем целую часть про­из­ве­де­ния для файла A, во вто­рой стро­ке  — ана­ло­гич­ные дан­ные для файла Б.

Воз­мож­ные дан­ные од­но­го из фай­лов ил­лю­стри­ро­ва­ны гра­фи­ком.

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

Ответ: