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

	П1	П2	П3	П4	П5	П6	П7	П8	П9
П1
П2
П3
П4
П5
П6
П7
П8
П9

Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Вы­пи­ши­те по­сле­до­ва­тель­но без про­бе­лов и зна­ков пре­пи­на­ния ука­зан­ные на графе бук­вен­ные обо­зна­че­ния пунк­тов от П1 до П9: сна­ча­ла букву, со­от­вет­ству­ю­щую П1, затем букву, со­от­вет­ству­ю­щую П2, и т. д.

Миша за­пол­нял таб­ли­цу ис­тин­но­сти ло­ги­че­ской функ­ции F

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

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

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

При­мер. Функ­ция F за­да­на вы­ра­же­ни­ем ¬x ∨ y, за­ви­ся­щим от двух

пе­ре­мен­ных, а фраг­мент таб­ли­цы имеет сле­ду­ю­щий вид.

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

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

Таб­ли­ца «Дви­же­ние то­ва­ров» со­дер­жит за­пи­си о по­став­ках то­ва­ров в ма­га­зи­ны в те­че­ние пер­вой де­ка­ды июня 2021 г., а также ин­фор­ма­цию о про­дан­ных то­ва­рах. Поле Тип опе­ра­ции со­дер­жит зна­че­ние По­ступ­ле­ние или Про­да­жа, а в со­от­вет­ству­ю­щее поле Ко­ли­че­ство упа­ко­вок, шт. за­не­се­на ин­фор­ма­ция о том, сколь­ко упа­ко­вок то­ва­ра по­сту­пи­ло в ма­га­зин или было про­да­но в те­че­ние дня. За­го­ло­вок таб­ли­цы имеет сле­ду­ю­щий вид.

Таб­ли­ца «Товар» со­дер­жит ин­фор­ма­цию об ос­нов­ных ха­рак­те­ри­сти­ках каж­до­го то­ва­ра. За­го­ло­вок таб­ли­цы имеет сле­ду­ю­щий вид.

Таб­ли­ца «Ма­га­зин» со­дер­жит ин­фор­ма­цию о ме­сто­на­хож­де­нии ма­га­зи­нов. За­го­ло­вок таб­ли­цы имеет сле­ду­ю­щий вид.

На ри­сун­ке при­ве­де­на схема ука­зан­ной базы дан­ных.

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

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

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, К, Л, О, C, Т ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, для ко­то­ро­го вы­пол­ня­ет­ся усло­вие Фано. Для букв А и К ис­поль­зо­ва­ли со­от­вет­ствен­но ко­до­вые слова 10, 111. Най­ди­те ко­до­вую по­сле­до­ва­тель­ность наи­мень­шей длины для ко­ди­ро­ва­ния слова КО­ЛО­КОЛ и за­пи­ши­те по­лу­чен­ный ре­зуль­тат в вось­ме­рич­ном коде. Если таких кодов не­сколь­ко, ука­жи­те код с наи­мень­шим чис­ло­вым зна­че­ни­ем.

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

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

2.  К этой за­пи­си до­пи­сы­ва­ют­ся ещё не­сколь­ко раз­ря­дов по сле­ду­ю­ще­му пра­ви­лу:

3.  а)  если N чётное, то к нему спра­ва при­пи­сы­ва­ет­ся один ноль, а слева еди­ни­ца и ноль;

4.  б)  если N нечётное, то к нему спра­ва при­пи­сы­ва­ет­ся в дво­ич­ном виде сумма цифр его дво­ич­ной за­пи­си;

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

На­при­мер, ис­ход­ное число 4₁₀  =  100₂ пре­об­ра­зу­ет­ся в число 101000₂  =  40₁₀, а ис­ход­ное число 13₁₀  =  1101₂ пре­об­ра­зу­ет­ся в число 110111₂  =  55₁₀.

Ука­жи­те такое число N, для ко­то­ро­го число R яв­ля­ет­ся наи­мень­шим среди чисел, пре­вы­ша­ю­щих 600. В от­ве­те это число за­пи­ши­те в де­ся­тич­ной си­сте­ме счис­ле­ния.

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

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

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

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

Му­зы­каль­ный фраг­мент был за­пи­сан в фор­ма­те моно, оциф­ро­ван и со­хранён в виде файла без ис­поль­зо­ва­ния сжа­тия дан­ных. Затем тот же му­зы­каль­ный фраг­мент был за­пи­сан по­втор­но в фор­ма­те сте­рео (двух­ка­наль­ная за­пись) и оциф­ро­ван с раз­ре­ше­ни­ем в 3 раза боль­ше и ча­сто­той дис­кре­ти­за­ции в 4 раза мень­ше, чем в пер­вый раз. При этом про­из­во­ди­лось сжа­тие дан­ных, объем сжа­то­го фраг­мен­та на 40% мень­ше ис­ход­но­го. Раз­мер по­лу­чен­но­го файла  — 18 Мбайт. Ука­жи­те раз­мер файла в Мбайт, по­лу­чен­но­го при на­чаль­ной за­пи­си. В от­ве­те за­пи­ши­те толь­ко целое число, еди­ни­цу из­ме­ре­ния пи­сать не нужно.

Все 5-⁠бук­вен­ные слова, со­став­лен­ные из 5 букв А, К, Л, О, Ш, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке.

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

1.  ААААА

2.  ААААК

3.  ААААЛ

4.  ААААО

5.  ААААШ

6.  АААКА

...

На каком месте от на­ча­ла спис­ка стоит слово ШКОЛА?

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

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

—  наи­боль­шее из 4 чисел мень­ше суммы трёх дру­гих;

—  все че­ты­ре числа раз­лич­ны.

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

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

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

Си­сте­ма от­пра­ви­ла три со­об­ще­ния по 33 сим­во­ла каж­дое и шесть со­об­ще­ний по 29 сим­во­лов. При этом всего было пе­ре­да­но более 330 байт.

Какое наи­мень­шее число бай­тов может со­дер­жать за­го­ло­вок со­об­ще­ния? В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство бай­тов.

Ис­пол­ни­тель Ре­дак­тор по­лу­ча­ет на вход стро­ку цифр и пре­об­ра­зу­ет её. Ре­дак­тор может вы­пол­нять две ко­ман­ды, в обеих ко­ман­дах v и w обо­зна­ча­ют це­поч­ки цифр.

А)  за­ме­нить (v, w).

Эта ко­ман­да за­ме­ня­ет в стро­ке пер­вое слева вхож­де­ние це­поч­ки v на це­поч­ку w. На­при­мер, вы­пол­не­ние ко­ман­ды

за­ме­нить (111, 27)

пре­об­ра­зу­ет стро­ку 05111150 в стро­ку 0527150.

Если в стро­ке нет вхож­де­ний це­поч­ки v, то вы­пол­не­ние ко­ман­ды за­ме­нить (v, w) не ме­ня­ет эту стро­ку.

Б)  на­шлось (v).

Эта ко­ман­да про­ве­ря­ет, встре­ча­ет­ся ли це­поч­ка v в стро­ке ис­пол­ни­те­ля Ре­дак­тор. Если она встре­ча­ет­ся, то ко­ман­да воз­вра­ща­ет ло­ги­че­ское зна­че­ние «ис­ти­на», в про­тив­ном слу­чае воз­вра­ща­ет зна­че­ние «ложь». Стро­ка ис­пол­ни­те­ля при этом не из­ме­ня­ет­ся.

Дана про­грам­ма для Ре­дак­то­ра:

НА­ЧА­ЛО

    ПОКА на­шлось (111) ИЛИ на­шлось (222)

            за­ме­нить (111, 22)

            за­ме­нить (222, 11)

            за­ме­нить (11, 2)

            за­ме­нить (22, 1)

    КОНЕЦ ПОКА

КОНЕЦ

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

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

По за­дан­ным IP-⁠ад­ре­су узла и маске опре­де­ли­те адрес сети.

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

Маска: 255.255.252.0

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

При­мер.

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

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

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

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

На чис­ло­вой пря­мой даны три от­рез­ка: P  =  [24; 77], Q [47; 92] и R  =  [82; 116].

Ука­жи­те наи­мень­шую воз­мож­ную длину та­ко­го от­рез­ка A, для ко­то­ро­го фор­му­ла

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

F(a, 0)  =  a;

F(a, b)  =  F(a−1, b) + b, если a ≥ b;

F(a, b)  =  F(a, b−1) + a, если a < b и b > 0.

Ука­жи­те ко­ли­че­ство таких целых не­от­ри­ца­тель­ных чисел a, для ко­то­рых можно по­до­брать такое b, что F(a, b)  =  1 048 576.

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

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

—  в трой­ке есть четырёхзнач­ные числа;

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

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

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

Ответ:

Квад­рат раз­ли­но­ван на N × N кле­ток Ис­пол­ни­тель Робот может пе­ре­ме­щать­ся по клет­кам, вы­пол­няя за одно пе­ре­ме­ще­ние одну из двух ко­манд: впра­во или вниз. По ко­ман­де впра­во Робот пе­ре­ме­ща­ет­ся в со­сед­нюю пра­вую клет­ку, по ко­ман­де вниз  — в со­сед­нюю ниж­нюю.

Квад­рат огра­ни­чен внеш­ни­ми сте­на­ми. Между со­сед­ни­ми клет­ка­ми квад­ра­та также могут быть внут­рен­ние стены. Сквозь стену Робот прой­ти не может.

Перед каж­дым за­пус­ком Ро­бо­та в каж­дой клет­ке квад­ра­та лежит мо­не­та до­сто­ин­ством от 1 до 100. По­се­тив клет­ку, Робот за­би­ра­ет мо­не­ту с собой; это также от­но­сит­ся к на­чаль­ной и ко­неч­ной клет­кам марш­ру­та Ро­бо­та. В «уг­ло­вых» клет­ках поля  — тех, ко­то­рые спра­ва и снизу огра­ни­че­ны сте­на­ми, Робот не может про­дол­жать дви­же­ние, по­это­му на­коп­лен­ная сумма счи­та­ет­ся ито­го­вой. Таких ко­неч­ных кле­ток на поле может быть не­сколь­ко, вклю­чая пра­вую ниж­нюю клет­ку поля. При раз­ных за­пус­ках ито­го­вые на­коп­лен­ные суммы могут раз­ли­чать­ся.

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

Ис­ход­ные дан­ные пред­став­ля­ют собой элек­трон­ную таб­ли­цу раз­ме­ром N × N, каж­дая ячей­ка ко­то­рой со­от­вет­ству­ет клет­ке квад­ра­та. Внут­рен­ние и внеш­ние стены обо­зна­че­ны утолщёнными ли­ни­я­ми.

Для та­ко­го ла­би­рин­та ответ будет 42 16.

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

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

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

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

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

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

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

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

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

усло­вия:

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

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

Если най­де­но не­сколь­ко зна­че­ний S, в от­ве­те ука­жи­те наи­мень­шее из них.

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

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

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

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

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

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

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

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

3.  При­ба­вить 2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В файле Б хра­нят­ся дан­ные о звёздах трёх кла­сте­ров, где H  =  6, W  =  5 для каж­до­го кла­сте­ра. Из­вест­но, что ко­ли­че­ство звёзд не пре­вы­ша­ет 10 000.

Струк­ту­ра хра­не­ния ин­фор­ма­ции в файле Б ана­ло­гич­на струк­ту­ре в файле А.

Из­вест­но, что в файле Б име­ют­ся ко­ор­ди­на­ты ровно трёх «лиш­них» точек, пред­став­ля­ю­щих ано­ма­лии, ко­то­рые воз­ник­ли в ре­зуль­та­те помех при пе­ре­да­че дан­ных. Эти три точки не от­но­сят­ся ни к од­но­му из кла­сте­ров, их учи­ты­вать не нужно.

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

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

Га­ран­ти­ру­ет­ся, что во всех кла­сте­рах ко­ли­че­ство точек раз­лич­но.

В от­ве­те за­пи­ши­те че­ты­ре числа: в пер­вой стро­ке  — сна­ча­ла целую часть аб­со­лют­ной ве­ли­чи­ны про­из­ве­де­ния Px × 10 000, затем целую часть аб­со­лют­ной ве­ли­чи­ны про­из­ве­де­ния Py × 10 000; во вто­рой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния Q₁ × 10 000, затем целую часть про­из­ве­де­ния Q₂ × 10 000.

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

Ответ: