На ри­сун­ке спра­ва схема дорог Н-⁠ского рай­о­на изоб­ра­же­на в виде графа; в таб­ли­це слева со­дер­жат­ся све­де­ния о про­тяжённо­сти каж­дой из этих дорог (в ки­ло­мет­рах).

Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, то ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Опре­де­ли­те, ка­ко­ва длина до­ро­ги из пунк­та Г в пункт Е. В от­ве­те за­пи­ши­те целое число  — так, как оно ука­за­но в таб­ли­це.

Ло­ги­че­ская функ­ция F задаётся вы­ра­же­ни­ем (y → z) ∧ ¬((y ∨ w) → (z ∧ x)). На ри­сун­ке при­ведён ча­стич­но за­пол­нен­ный фраг­мент таб­ли­цы ис­тин­но­сти функ­ции F, со­дер­жа­щий не­по­вто­ря­ю­щи­е­ся стро­ки. Опре­де­ли­те, ка­ко­му столб­цу таб­ли­цы ис­тин­но­сти функ­ции F со­от­вет­ству­ет каж­дая из пе­ре­мен­ных x, y, z, w.

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

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

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

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

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

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

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

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

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

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

Для пе­ре­да­чи дан­ных ис­поль­зу­ет­ся дво­ич­ный код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б, В или Г, для букв А, Б и В ис­поль­зу­ют­ся сле­ду­ю­щие ко­до­вые слова: A  — 0, Б  — 101, В  — 111.

Най­ди­те ко­до­вое слово ми­ни­маль­ной длины для Г, при ко­то­ром со­хра­ня­ет­ся пря­мое усло­вие Фано. Если таких ко­до­вых слов не­сколь­ко, ука­жи­те ко­до­вое слово с ми­ни­маль­ным дво­ич­ным зна­че­ни­ем.

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

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

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

2.  В конец дво­ич­ной за­пи­си до­бав­ля­ет­ся дво­ич­ный код остат­ка от де­ле­ния числа N на 4.

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

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

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

2.  Оста­ток от де­ле­ния 13 на 4 равен 1, до­бав­ля­ем к дво­ич­ной за­пи­си цифру 1, по­лу­ча­ем 11011₂  =  27₁₀.

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

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

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

2.  Оста­ток от де­ле­ния 14 на 4 равен 2, до­бав­ля­ем к дво­ич­ной за­пи­си цифры 10 (10₂  =  2₁₀), по­лу­ча­ем 111010₂  =  58₁₀.

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

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

Какое наи­боль­шее ко­ли­че­ство до­ступ­ных чисел может быть на от­рез­ке, со­дер­жа­щем 49 на­ту­раль­ных чисел?

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

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

Че­ре­па­хе был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм: По­вто­ри 7 [Вперёд 10 На­пра­во 120].

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

Аудио­по­ток ко­ди­ру­ет­ся в ре­жи­ме сте­рео (2 ка­на­ла) с ча­сто­той дис­кре­ти­за­ции 32 кГц и пе­ре­даётся по ка­на­лу с про­пуск­ной спо­соб­но­стью 40 Кбайт/⁠сек. При этом ис­поль­зу­ют­ся ме­то­ды сжа­тия, ко­то­рые поз­во­ля­ют со­кра­тить объём пе­ре­да­ва­е­мой ин­фор­ма­ции на 68%. С какой мак­си­маль­ной глу­би­ной ко­ди­ро­ва­ния можно вести за­пись?

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

Вася со­став­ля­ет 4-⁠бук­вен­ные слова, в ко­то­рых есть толь­ко буквы Б, Р, О, Н, Х, И, причём буква Х ис­поль­зу­ет­ся в каж­дом слове, и толь­ко 1 раз. Каж­дая из дру­гих до­пу­сти­мых букв может встре­чать­ся в слове любое ко­ли­че­ство раз или не встре­чать­ся со­всем. Сло­вом счи­та­ет­ся любая до­пу­сти­мая по­сле­до­ва­тель­ность букв, не обя­за­тель­но осмыс­лен­ная. Сколь­ко су­ще­ству­ет таких слов, ко­то­рые может на­пи­сать Вася?

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

—  в стро­ке встре­ча­ет­ся ровно че­ты­ре раз­лич­ных числа; два из них по два раза, два  — по од­но­му;

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

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

C по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз встре­ча­ет­ся слово «его» или «Его» в тек­сте пер­вых двух глав ро­ма­на И. С. Тур­ге­не­ва «Отцы и дети». Дру­гие формы этого слова учи­ты­вать не сле­ду­ет.

В от­ве­те ука­жи­те толь­ко число.

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 20 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы из 8-⁠сим­воль­но­го на­бо­ра: А, В, C, D, Е, F, G, H. В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Кроме соб­ствен­но па­ро­ля для каж­до­го поль­зо­ва­те­ля в си­сте­ме хра­нят­ся до­пол­ни­тель­ные све­де­ния, для чего вы­де­ле­но 12 байт на каж­до­го поль­зо­ва­те­ля.

Сколь­ко байт нужно для хра­не­ния све­де­ний о 25 поль­зо­ва­те­лях? В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство байт.

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

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

Эта ко­ман­да за­ме­ня­ет в стро­ке пер­вое слева вхож­де­ние це­поч­ки v на це­поч­ку w. На­при­мер, вы­пол­не­ние ко­ман­ды за­ме­нить (111, 27) пре­об­ра­зу­ет стро­ку 05111150 в стро­ку 0527150.

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

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

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

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

НА­ЧА­ЛО

                ПОКА НЕ на­шлось (00)

                        за­ме­нить (02, 101)

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

                        за­ме­нить (012, 30)

                        за­ме­нить (010, 00)

                КОНЕЦ ПОКА

КОНЕЦ

Из­вест­но, что ис­ход­ная стро­ка A со­дер­жа­ла ровно два нуля  — на пер­вом и на по­след­нем месте, 40 еди­ниц, боль­ше 40 двоек и не со­дер­жа­ла дру­гих цифр.

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

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

Сеть за­да­на IP-⁠ад­ре­сом 122.159.136.144 и мас­кой сети 255.255.255.248.

Сколь­ко в этой сети IP-⁠ад­ре­сов, для ко­то­рых ко­ли­че­ство еди­ниц в дво­ич­ной за­пи­си IP-⁠ад­ре­са не крат­но 4?

В от­ве­те ука­жи­те толь­ко число.

Зна­че­ние вы­ра­же­ния 4³⁶ + 3 · 4²⁰ + 4¹⁵ + 2 · 4⁷ + 49 за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 16. Сколь­ко раз­ных цифр встре­ча­ет­ся в этой за­пи­си?

Для ка­ко­го наи­боль­ше­го це­ло­го по­ло­жи­тель­но­го числа А вы­ра­же­ние

тож­де­ствен­но ис­тин­но, то есть при­ни­ма­ет зна­че­ние 1 при любых целых не­от­ри­ца­тель­ных x и y?

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

F(1)  =  1;

F(2)  =  2;

F(3)  =  3;

F(n)  =  F(n − 3) · n при n > 3.

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

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

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

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

—  хотя бы одно число в трой­ке де­лит­ся на 3;

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

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

Ответ:

Робот стоит в левом верх­нем углу пря­мо­уголь­но­го поля, в каж­дой клет­ке ко­то­ро­го за­пи­са­но целое по­ло­жи­тель­ное число. За один ход робот может пе­ре­ме­стить­ся на одну клет­ку впра­во, вниз, по диа­го­на­ли впра­во-вниз или по диа­го­на­ли влево-⁠вниз. Числа по­ка­зы­ва­ют рас­ход энер­гии ро­бо­та на про­хож­де­ние клет­ки.

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

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це. При­мер вход­ных дан­ных (для таб­ли­цы раз­ме­ром 4 × 4):

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

а мак­си­маль­ный  — при дви­же­нии по марш­ру­ту:

В от­ве­те в дан­ном слу­чае надо за­пи­сать числа 177 и 577.

Ответ:

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

Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 43.

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

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

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

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

Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 43.

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

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

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

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

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

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

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

Ответ:

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

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

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

Если най­де­но не­сколь­ко зна­че­ний 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

3.  Умножь на 2

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

Тек­сто­вый файл со­сто­ит не более, чем из 1 200 000 сим­во­лов ан­глий­ско­го ал­фа­ви­та.

Опре­де­ли­те мак­си­маль­ное ко­ли­че­ство иду­щих под­ряд сим­во­лов, среди ко­то­рых сим­во­лы Q, R, S в раз­лич­ных ком­би­на­ци­ях (с учётом по­вто­ре­ний) не стоят рядом.

Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му.

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

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

В пер­вой стро­ке вход­но­го файла на­хо­дят­ся три числа: N  — ко­ли­че­ство за­ня­тых мест в зале (целое по­ло­жи­тель­ное число, не пре­вы­ша­ю­щее 10 000), М  — ко­ли­че­ство рядов (целое по­ло­жи­тель­ное число, не пре­вы­ша­ю­щее 100 000) и K  — ко­ли­че­ство мест в каж­дом ряду (целое по­ло­жи­тель­ное число, не пре­вы­ша­ю­щее 100 000). В сле­ду­ю­щих N стро­ках на­хо­дят­ся пары на­ту­раль­ных чисел: номер ряда и номер места за­ня­то­го крес­ла со­от­вет­ствен­но (пер­вое число не пре­вы­ша­ет зна­че­ния M, а вто­рое  — K).

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

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

Ответ:

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

Га­ран­ти­ру­ет­ся, что такое раз­би­е­ние су­ще­ству­ет и един­ствен­но.

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

В файле А хра­нят­ся дан­ные о звёздах трёх кла­сте­ров, для ко­то­рых цен­тром окруж­но­сти яв­ля­ет­ся точка C(5, –9). В каж­дой стро­ке за­пи­са­на ин­фор­ма­ция о рас­по­ло­же­нии на карте одной звез­ды: сна­ча­ла ко­ор­ди­на­та х, затем ко­ор­ди­на­та у. Зна­че­ния даны в услов­ных еди­ни­цах. Из­вест­но, что ко­ли­че­ство звёзд не пре­вы­ша­ет 1000.

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

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

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

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

Ответ: