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

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

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

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

При­мер. Функ­ция F за­да­на вы­ра­же­ни­ем ¬ x ∨ y, за­ви­ся­щее от двух пе­ре­мен­ных, а фраг­мент таб­ли­цы имеет сле­ду­ю­щий вид:

В этом слу­чае пер­во­му столб­цу со­от­вет­ству­ет пе­ре­мен­ная y, а вто­ро­му столб­цу  — пе­ре­мен­ная х. B от­ве­те сле­ду­ет на­пи­сать: ух.

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

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся шиф­ро­ван­ные со­об­ще­ния, со­дер­жа­щие толь­ко во­семь букв: A, Б, B, Г, Д, Е, Ж, 3. Для пе­ре­да­чи ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для шести букв ис­поль­зу­ют­ся ко­до­вые слова.

Какое наи­мень­шее ко­ли­че­ство дво­ич­ных зна­ков по­тре­бу­ет­ся для ко­ди­ро­ва­ния двух остав­ших­ся букв? В от­ве­те за­пи­ши­те сум­мар­ную длину ко­до­вых слов для букв: А; Б.

При­ме­ча­ние.

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

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

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

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

а)  если число N де­лит­ся на 3, то в этой за­пи­си до­пи­сы­ва­ют­ся спра­ва три по­след­ние дво­ич­ные цифры;

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

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

3.  Ре­зуль­тат пе­ре­во­дит­ся в де­ся­тич­ную си­сте­му и вы­во­дит­ся на экран.

На­при­мер, для ис­ход­но­го числа 12  =  1100₂, ре­зуль­та­том яв­ля­ет­ся число 1100100₂  =  100, а для ис­ход­но­го числа 4  =  100₂ ре­зуль­та­том яв­ля­ет­ся число 10011₂  =  19.

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

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

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

По­вто­ри 2 [Вперёд 10 На­пра­во 90 Вперёд 18 На­пра­во 90]

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

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

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

По­вто­ри 2 [Вперёд 10 На­пра­во 90 Вперёд 7 На­пра­во 90].

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

Сколь­ко се­кунд по­тре­бу­ет­ся обыч­но­му мо­де­му, пе­ре­да­ю­ще­му со­об­ще­ния со ско­ро­стью 65 536 бит/⁠с, чтобы пе­ре­дать цвет­ное раст­ро­вое изоб­ра­же­ние раз­ме­ром 1024 на 768 пик­се­лей, при усло­вии, что цвет каж­до­го пик­се­ля ко­ди­ру­ет­ся 3 бай­та­ми?

Все ше­сти­бук­вен­ные слова, со­став­лен­ные из букв M, A, Н, Г, У, C, T, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке и про­ну­ме­ро­ва­ны.

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

1.  AAAAAA

2.  AAAAAГ

3.  AAAAAM

4.  AAAAAH

5.  AAAAAC

6.  AAAAAT

7.  АААА­АУ

...

Под каким но­ме­ром в спис­ке стоит по­след­нее слово, ко­то­рое не на­чи­на­ет­ся с буквы У, со­дер­жит толь­ко две буквы M и нe более одной буквы Г.

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

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

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

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

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

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му объ­ек­ту при­сва­и­ва­ет­ся иден­ти­фи­ка­тор, со­сто­я­щий из 105 сим­во­лов и со­дер­жа­щий толь­ко де­ся­тич­ные цифры и сим­во­лы из 1500-⁠сим­воль­но­го спе­ци­аль­но­го ал­фа­ви­та. В базе дан­ных для хра­не­ния све­де­ний о каж­дом иден­ти­фи­ка­то­ре от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние иден­ти­фи­ка­то­ров, все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит.

Опре­де­ли­те объём па­мя­ти (в Кбайт), не­об­хо­ди­мый для хра­не­ния све­де­ний о 16 384 объ­ек­тах. В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство Кбайт.

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

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

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

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

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

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

Цикл:

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

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

КОНЕЦ ПОКА

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

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

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

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

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

КОНЕЦ ЕСЛИ

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

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

НА­ЧА­ЛО

ПОКА на­шлось (72) ИЛИ на­шлось (522) ИЛИ на­шлось (2222)

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

      ТО за­ме­нить (72, 2)

    КОНЕЦ ЕСЛИ

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

       ТО за­ме­нить (522, 27)

КОНЕЦ ЕСЛИ

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

     ТО за­ме­нить (2222, 5)

   КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

На вход при­ведённой выше про­грам­ме по­сту­па­ет стро­ка, на­чи­на­ю­ща­я­ся с цифры 5, а затем со­дер­жа­щая n цифр 2 (3 < n < 10 000).

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

На ри­сун­ке пред­став­ле­на схема дорог, свя­зы­ва­ю­щих го­ро­да A, Б, B, Г, Д, Е, Ж, И, K, Л. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.

Ка­ко­ва длина са­мо­го про­тяжённого пути из пунк­та А в пункт Л. Дли­ной пути счи­тать ко­ли­че­ство дорог, со­став­ля­ю­щих этот путь.

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

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

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

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

F(n)  =  n, при n < 11;

F(n)  =  n + F(n − 1), если n ≥ 11.

Чему равно зна­че­ние вы­ра­же­ния F(2024) − F(2021)?

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

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

Ответ:

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

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

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

Ти­по­вой при­мер имеет ил­лю­стри­ро­ван­ный ха­рак­тер. Для вы­пол­не­ния за­да­ния ис­поль­зуй­те дан­ные из при­ла­га­е­мо­го файла.

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

У ис­пол­ни­те­ля есть три ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра. А.  При­ба­вить 2.

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

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

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

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

Тра­ек­то­рия вы­чис­ле­ний про­грам­мы  — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы СВА при ис­ход­ном числе 7 тра­ек­то­рия со­сто­ит из чисел 14, 17, 19.

Тек­сто­вый файл со­сто­ит из сим­во­лов T, U, V, W, X, Y и Z.

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

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

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

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

В пер­вой стро­ке вход­но­го файла на­хо­дит­ся на­ту­раль­ное число N (N < 1000)  — ко­ли­че­ство за­явок на про­ве­де­ние ме­ро­при­я­тий.

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

За­пи­ши­те в от­ве­те два числа: мак­си­маль­ное  — ко­ли­че­ство ме­ро­при­я­тий, ко­то­рое можно про­ве­сти в кон­фе­ренц-зале и самое позд­нее время окон­ча­ния по­след­не­го ме­ро­при­я­тия (в ми­ну­тах от на­ча­ла суток).

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

5

10 150

100 110

131 170

131 180

120 130

При таких ис­ход­ных дан­ных можно про­ве­сти мак­си­мум три ме­ро­при­я­тия, на­при­мер, по за­яв­кам 2, 3 и 5. Кон­фе­ренц-⁠зал осво­бо­дит­ся самое позд­нее на 180-⁠й ми­ну­те, если со­сто­ят­ся ме­ро­при­я­тия по за­яв­кам 2, 4, 5.

Ти­по­вой при­мер имеет ил­лю­стра­тив­ный ха­рак­тер. Для вы­пол­не­ния за­да­ния ис­поль­зуй­те дан­ные из при­ла­га­е­мых фай­лов.

Ответ:

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

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

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит на­ту­раль­ное число К  — ми­ни­маль­ное ко­ли­че­ство минут, ко­то­рое долж­но прой­ти между мо­мен­та­ми пе­ре­да­ча­ми любых двух из трёх по­ка­за­ний, а во вто­рой  — ко­ли­че­ство пе­ре­дан­ных по­ка­за­ний N (1 ≤  N 10 000 000, N > K). B каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10 000 000, ко­то­рое обо­зна­ча­ет зна­че­ние силы тока в со­от­вет­ству­ю­щую ми­ну­ту.

За­пи­ши­те в от­ве­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла A, затем  — для файла В.

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

2

6

15

14

20

23

21

10

При таких ис­ход­ных ис­ко­мая ве­ли­чи­на равна 45  — это сумма зна­че­ний, за­фик­си­ро­ван­ных на пер­вой, тре­тьей и ше­стой ми­ну­тах из­ме­ре­ний.

Ти­по­вой при­мер имеет ил­лю­стра­тив­ный ха­рак­тер. Для вы­пол­не­ния за­да­ния ис­поль­зуй­те дан­ные из при­ла­га­е­мых фай­лов.

Ответ: