На ри­сун­ке слева изоб­ра­же­на схема дорог N-⁠ского рай­о­на. В таб­ли­це звёздоч­кой обо­зна­че­но на­ли­чие до­ро­ги из од­но­го населённого пунк­та в дру­гой. От­сут­ствие звёздоч­ки озна­ча­ет, что такой до­ро­ги нет.

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

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

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

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

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

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

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

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

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

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

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

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

Все за­глав­ные буквы рус­ско­го ал­фа­ви­та за­ко­ди­ро­ва­ны не­рав­но­мер­ным дво­ич­ным кодом, в ко­то­ром ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это усло­вие обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: И  — 01, Н  — 110, Ф  — 00111, О  — 000, Р  — 111, М  — 10101, А  — 100, Т  — 0010, К  — 1011. Ука­жи­те воз­мож­ный код ми­ни­маль­ной длины для буквы Ю. Если таких кодов не­сколь­ко, ука­жи­те тот из них, ко­то­рый имеет ми­ни­маль­ное чис­ло­вое зна­че­ние.

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

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

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

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

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

1.  В де­ся­тич­ной за­пи­си вы­де­ля­ем трёхзнач­ные числа: 200, 002, 024.

2.  Наи­боль­шее из най­ден­ных чисел 200, наи­мень­шее 002.

3.  200 − 002  =  198.

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

При каком наи­мень­шем N в ре­зуль­та­те ра­бо­ты ал­го­рит­ма по­лу­чит­ся R  =  415?

Ис­пол­ни­тель Че­ре­па­ха дей­ству­ет на плос­ко­сти с де­кар­то­вой си­сте­мой ко­ор­ди­нат. В на­чаль­ный мо­мент Че­ре­па­ха на­хо­дит­ся в на­ча­ле ко­ор­ди­нат, её го­ло­ва на­прав­ле­на вдоль по­ло­жи­тель­но­го на­прав­ле­ния оси ор­ди­нат, хвост опу­щен. При опу­щен­ном хво­сте Че­ре­па­ха остав­ля­ет на поле след в виде линии. В каж­дый кон­крет­ный мо­мент из­вест­но по­ло­же­ние ис­пол­ни­те­ля и на­прав­ле­ние его дви­же­ния. У ис­пол­ни­те­ля су­ще­ству­ет две ко­ман­ды: Вперёд n (где n  — целое число), вы­зы­ва­ю­щая пе­ре­дви­же­ние Че­ре­па­хи на n еди­ниц в том на­прав­ле­нии, куда ука­зы­ва­ет её го­ло­ва, и На­пра­во m (где m  — целое число), вы­зы­ва­ю­щая из­ме­не­ние на­прав­ле­ния дви­же­ния на m гра­ду­сов по ча­со­вой стрел­ке. За­пись По­вто­ри k [Ко­ман­да1 Ко­ман­да2 … Ко­ман­даS] озна­ча­ет, что по­сле­до­ва­тель­ность из S ко­манд по­вто­рит­ся k раз. Че­ре­па­хе был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм:

По­вто­ри 4 [Вперёд 9 На­пра­во 90]

По­вто­ри 3 [Вперёд 9 На­пра­во 120].

Опре­де­ли­те, сколь­ко точек с це­ло­чис­лен­ны­ми ко­ор­ди­на­та­ми будут на­хо­дить­ся внут­ри об­ла­сти, огра­ни­чен­ной ли­ни­ей, за­дан­ной дан­ным ал­го­рит­мом По­вто­ри 4 [Вперёд 9 На­пра­во 90] и на­хо­дить­ся вне об­ла­сти, огра­ни­чен­ной ли­ни­ей, за­дан­ной дан­ным ал­го­рит­мом: По­вто­ри 3 [Вперёд 9 На­пра­во 120]. Точки на линии учи­ты­вать не сле­ду­ет.

В ин­фор­ма­ци­он­ной си­сте­ме хра­нят­ся изоб­ра­же­ния раз­ме­ром 512 × 280 пк. При ко­ди­ро­ва­нии ис­поль­зу­ет­ся ал­го­ритм сжа­тия изоб­ра­же­ний, поз­во­ля­ю­щий умень­шить раз­мер па­мя­ти для хра­не­ния од­но­го изоб­ра­же­ния в сред­нем на 25% по срав­не­нию с не­за­ви­си­мым ко­ди­ро­ва­ни­ем каж­до­го пик­се­ля. Каж­дое сжа­тое изоб­ра­же­ние до­пол­ня­ет­ся слу­жеб­ной ин­фор­ма­ци­ей, ко­то­рая за­ни­ма­ет 32 Кбайт. Для хра­не­ния 64 изоб­ра­же­ний по­тре­бо­ва­лось 16 Мбайт. Сколь­ко цве­тов ис­поль­зо­ва­но в па­лит­ре каж­до­го изоб­ра­же­ния?

Пётр со­став­ля­ет таб­ли­цу ко­до­вых слов для пе­ре­да­чи со­об­ще­ний, каж­до­му со­об­ще­нию со­от­вет­ству­ет своё ко­до­вое слово. В ка­че­стве ко­до­вых слов Пётр ис­поль­зу­ет все пя­ти­бук­вен­ные слова в ал­фа­ви­те {A, B, C, D, E, F}, удо­вле­тво­ря­ю­щие та­ко­му усло­вию: ко­до­вое слово не может на­чи­нать­ся с буквы F и за­кан­чи­вать­ся бук­вой A. Сколь­ко раз­лич­ных ко­до­вых слов может ис­поль­зо­вать Пётр?

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

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

—  сред­нее ариф­ме­ти­че­ское наи­боль­ше­го и наи­мень­ше­го чисел в стро­ке боль­ше сред­не­го ариф­ме­ти­че­ско­го всех осталь­ных чисел.

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

Опре­де­ли­те, сколь­ко раз, не счи­тая сно­сок, в тек­сте про­из­ве­де­ния А. С. Пуш­ки­на «Ка­пи­тан­ская дочка» встре­ча­ет­ся слово «Москва» в любом па­де­же.

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме для каж­до­го поль­зо­ва­те­ля фор­ми­ру­ет­ся ин­ди­ви­ду­аль­ный иден­ти­фи­ка­тор, со­сто­я­щий из 14 сим­во­лов. Для по­стро­е­ния иден­ти­фи­ка­то­ра ис­поль­зу­ют толь­ко строч­ные ла­тин­ские буквы (26 букв). В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние иден­ти­фи­ка­то­ров, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Кроме иден­ти­фи­ка­то­ра для каж­до­го поль­зо­ва­те­ля в си­сте­ме хра­нят­ся до­пол­ни­тель­ные све­де­ния, для чего вы­де­ле­но оди­на­ко­вое целое ко­ли­че­ство байт на каж­до­го поль­зо­ва­те­ля. Для хра­не­ния ин­фор­ма­ции о 25 поль­зо­ва­те­лях по­тре­бо­ва­лось 600 байт. Сколь­ко байт вы­де­ле­но для хра­не­ния до­пол­ни­тель­ных све­де­ний об одном поль­зо­ва­те­ле? В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство байт.

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

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

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

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

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

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

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

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

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

НА­ЧА­ЛО

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

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

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

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

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

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

    КОНЕЦ ПОКА

КОНЕЦ

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

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

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

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

Маска: 255.255.192.0

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

При­мер.

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

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

Зна­че­ние ариф­ме­ти­че­ско­го вы­ра­же­ния 16¹⁸ · 4¹⁰ − 4⁶ − 16 за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 4. Сколь­ко цифр 3 со­дер­жит­ся в этой за­пи­си?

На чис­ло­вой пря­мой даны два от­рез­ка: P  =  [15; 40] и Q  =  [21; 63]. Ука­жи­те наи­мень­шую воз­мож­ную длину та­ко­го от­рез­ка A, для ко­то­ро­го ло­ги­че­ское вы­ра­же­ние

ис­тин­но (т. е. при­ни­ма­ет зна­че­ние 1) при любом зна­че­нии пе­ре­мен­ной х.

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

F(1)  =  1;

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

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

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел. Её эле­мен­ты могут при­ни­мать целые зна­че­ния от −100 000 до 100 000 вклю­чи­тель­но.

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

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

Ответ:

Квад­рат раз­ли­но­ван на N х N кле­ток (1 < N < 30). Ис­пол­ни­тель Робот может пе­ре­ме­щать­ся по клет­кам, вы­пол­няя за одно пе­ре­ме­ще­ние одну из двух ко­манд: впра­во или вниз. По ко­ман­де впра­во Робот пе­ре­ме­ща­ет­ся в со­сед­нюю пра­вую клет­ку, по ко­ман­де вниз  — в со­сед­нюю ниж­нюю. Квад­рат огра­ни­чен внеш­ни­ми сте­на­ми.

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

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

Ответ:

В игре, опи­сан­ной в за­да­нии 19, в на­чаль­ный мо­мент в пер­вой куче было 17 кам­ней, а во вто­рой  — S кам­ней, 1 ≤ S ≤ 23.

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

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

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

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

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

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

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

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

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

Пер­вая ко­ман­да уве­ли­чи­ва­ет число на экра­не на 1, вто­рая уве­ли­чи­ва­ет его на 2, тре­тья умно­жа­ет на 3.

Про­грам­ма для ис­пол­ни­те­ля  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые пре­об­ра­зу­ют ис­ход­ное число 1 в число 15 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 8?

Тра­ек­то­рия вы­чис­ле­ний  — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 231 при ис­ход­ном числе 4 тра­ек­то­рия будет со­сто­ять из чисел 6, 18, 19.

Тек­сто­вый файл со­сто­ит из за­глав­ных букв ла­тин­ско­го ал­фа­ви­та А, В, C, D, Е и F. Опре­де­ли­те мак­си­маль­ное ко­ли­че­ство иду­щих под­ряд сим­во­лов в при­ла­га­е­мом файле, среди ко­то­рых пара сим­во­лов DE (в ука­зан­ном по­ряд­ке) встре­ча­ет­ся не более 240 раз. Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му.

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

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

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

На­при­мер, если t₁  =  10 и t ₂  =  15, то об­ра­бот­ка за­про­са на­ча­лась через 10 се­кунд после на­ча­ла суток и за­вер­ши­лась через 15 се­кунд после на­ча­ла суток, то есть дли­лась 5 се­кунд. Га­ран­ти­ру­ет­ся, что об­ра­бот­ка всех за­про­сов на­чи­на­ет­ся и за­кан­чи­ва­ет­ся в пре­де­лах одних суток, то есть 0 ≤ t₁ < t₂ ≤ 86400.

Опре­де­ли­те наи­боль­шее ко­ли­че­ство за­про­сов, ко­то­рые од­но­вре­мен­но на­хо­ди­лись в об­ра­бот­ке в пе­ри­од с 8:00 до 14:00, и общую про­дол­жи­тель­ность вре­ме­ни (в се­кун­дах) в этот пе­ри­од, в те­че­ние ко­то­ро­го вы­пол­ня­лось такое мак­си­маль­ное ко­ли­че­ство за­про­сов. За­про­сы, вы­пол­не­ние ко­то­рых по­па­ло в ука­зан­ный ин­тер­вал ча­стич­но, тоже сле­ду­ет учи­ты­вать.

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

Ответ:

Учёный решил про­ве­сти кла­сте­ри­за­цию не­ко­то­ро­го мно­же­ства звёзд по их рас­по­ло­же­нию на карте звёзд­но­го неба. Кла­стер звёзд  — это набор звёзд (точек) на гра­фи­ке. Каж­дая звез­да обя­за­тель­но при­над­ле­жит толь­ко од­но­му из кла­сте­ров. Центр кла­сте­ра, или цен­т­ро­ид,  — это одна из звёзд на гра­фи­ке, сумма рас­сто­я­ний от ко­то­рой до всех осталь­ных звёзд кла­сте­ра ми­ни­маль­на. Рас­сто­я­ние между двумя точ­ка­ми и вы­чис­ля­ет­ся по фор­му­ле:

Даны два вход­ных файла (файл 27A и файл 27Б). В файле 27A хра­нят­ся дан­ные о звёздах двух кла­сте­ров. В каж­дой стро­ке за­пи­са­на ин­фор­ма­ция о рас­по­ло­же­нии на карте одной звез­ды: ко­ор­ди­на­та x, затем ко­ор­ди­на­та y (в услов­ных еди­ни­цах). Из­вест­но, что ко­ли­че­ство звёзд не пре­вы­ша­ет 1000. В файле 27Б хра­нят­ся дан­ные о звёздах трёх кла­сте­ров.

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

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

Ответ: