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

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

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

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

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

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

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

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

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся шиф­ро­ван­ные со­об­ще­ния, со­дер­жа­щие толь­ко де­сять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для пе­ре­да­чи ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код. Для де­вя­ти букв ис­поль­зу­ют­ся ко­до­вые слова. Для буквы А  — 00, Е  — 010, И  — 011, К  — 1111, Л  — 1101, Р  — 1010, С  — 1110, Т  — 1011, У  — 100.

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

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

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

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

2.  Далее эта за­пись об­ра­ба­ты­ва­ет­ся по сле­ду­ю­ще­му пра­ви­лу:

а)  если сумма цифр в дво­ич­ной за­пи­си числа чётная, то к этой за­пи­си спра­ва до­пи­сы­ва­ет­ся 0, а затем два левых раз­ря­да за­ме­ня­ют­ся на 10;

б)  если сумма цифр в дво­ич­ной за­пи­си числа нечётная, то к этой за­пи­си спра­ва до­пи­сы­ва­ет­ся 1, а затем два левых раз­ря­да за­ме­ня­ют­ся на 11.

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

На­при­мер, для ис­ход­но­го числа 6₁₀  =  110₂ ре­зуль­та­том яв­ля­ет­ся число 1000₂  =  8₁₀, а для ис­ход­но­го числа 4₁₀  =  100₂ ре­зуль­та­том яв­ля­ет­ся число 1101₂  =  13₁₀.

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

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

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

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

Под­нять хвост

Вперёд 8 На­пра­во 90 Вперёд 7 На­ле­во 90

Опу­стить хвост

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

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

При­бор ав­то­ма­ти­че­ской фик­са­ции на­ру­ше­ний пра­вил до­рож­но­го по­ве­де­ния де­ла­ет цвет­ные фо­то­гра­фии раз­ме­ром 1024 × 768 пик­се­лей, ис­поль­зуя па­лит­ру из 4096 цве­тов. Для пе­ре­да­чи сним­ки груп­пи­ру­ют­ся в па­ке­ты по 256 штук. Опре­де­ли­те раз­мер од­но­го па­ке­та фо­то­гра­фий в Мбайт.

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

Опре­де­ли­те ко­ли­че­ство 9-⁠рич­ных 6-⁠знач­ных чисел, ко­то­рые не на­чи­на­ют­ся с не­чет­ных цифр, не окан­чи­ва­ют­ся циф­ра­ми 2 или 3, со­дер­жат не менее двух цифр 1.

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

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

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

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

C по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз встре­ча­ет­ся со­че­та­ние букв «рук» или «Рук» в тек­сте глав IV, V, VI и VII вто­рой части тома 2 ро­ма­на Л. Н. Тол­сто­го «Война и мир». В от­ве­те ука­жи­те толь­ко число.

B не­ко­то­рой стра­не ав­то­мо­биль­ный номер дли­ной 6 сим­во­лов со­став­ля­ют из за­глав­ных букв (ис­поль­зу­ют­ся толь­ко 33 раз­лич­ных буквы) и де­ся­тич­ных цифр в любом по­ряд­ке. Каж­дый такой номер в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством бай­тов (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством битов). Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 125 но­ме­ров. (Ответ дайте в бай­тах.)

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

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

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

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

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

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

Цикл

ПОКА усло­вие

по­сле­до­ва­тель­ность ко­манд

КОНЕЦ ПОКА

вы­пол­ня­ет­ся, пока усло­вие ис­тин­но.

В кон­струк­ции

ЕСЛИ усло­вие

ТО ко­ман­да1

ИНАЧЕ ко­ман­да2

КОНЕЦ ЕСЛИ

вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но) или ко­ман­да2 (если усло­вие ложно).

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

НА­ЧА­ЛО

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

ЕСЛИ на­шлось (33333)

ТО за­ме­нить (33333, 7)

ИНАЧЕ за­ме­нить (777, 3)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

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

Сеть за­да­на IP-ад­ре­сом 106.184.0.0 и мас­кой сети 255.248.0.0.

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

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

Зна­че­ние ариф­ме­ти­че­ско­го вы­ра­же­ния

за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 31. Опре­де­ли­те сумму цифр с чис­ло­вым зна­че­ни­ем, не пре­вы­ша­ю­щим 17, в за­пи­си этого числа.

Обо­зна­чим через ДЕЛ(n, m) утвер­жде­ние «на­ту­раль­ное число n де­лит­ся без остат­ка на на­ту­раль­ное число m».

Для ка­ко­го наи­мень­ше­го на­ту­раль­но­го числа А фор­му­ла

тож­де­ствен­но ис­тин­на (т. е. при­ни­ма­ет зна­че­ние 1) при любом целом по­ло­жи­тель­ном зна­че­нии пе­ре­мен­ной х?

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

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

F(n)  =  2 · n · F(n − 1), если n > 1.

Чему равно зна­че­ние вы­ра­же­ния (F(2024) − 4 · F(2023)) / F(2022)?

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

Ответ:

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

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Най­ди­те ми­ни­маль­ное зна­че­ние 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 мс.

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

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

A. Вычти 1

B. Вычти 2

C. Найди целую часть от де­ле­ния на 3

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

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

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

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

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

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

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

Ответ:

Пусть S  — по­сле­до­ва­тель­ность из N чисел про­ну­ме­ро­ван­ных под­ряд на­чи­ная с 1. Обо­зна­чим S_i, S_j, S_k три эле­мен­та по­сле­до­ва­тель­но­сти S, где i < j < k. Опре­де­ли­те в по­сле­до­ва­тель­но­сти S три таких числа S_i, S_j, S_k, что S_i > S_j, S_k > S_j и зна­че­ние вы­ра­же­ния (S_i − S_j) + (S_k − S_j) мак­си­маль­но. В от­ве­те ука­жи­те най­ден­ное мак­си­маль­ное зна­че­ние вы­ра­же­ния (S_i − S_j) + (S_k − S_j). Га­ран­ти­ру­ет­ся, что в по­сле­до­ва­тель­но­сти есть три числа S_i, S_j, S_k, удо­вле­тво­ря­ю­щие усло­вию за­да­чи.

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

Дано два вход­ных файла (файл А и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит число N (5 < N <10 000 000)  — ко­ли­че­ство целых чисел. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно целое число, зна­че­ние ко­то­ро­го по мо­ду­лю не пре­вы­ша­ет 1000. В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла А, затем  — для файла B.

Ответ: