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

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

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

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

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

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

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

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

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко че­ты­ре буквы: А, Б, В, Г. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Ко­до­вые слова для букв из­вест­ны: А  — 0, Б  — 1111, В  — 1010. Най­ди­те код ми­ни­маль­ной длины для буквы Г. Если таких кодов не­сколь­ко, ука­жи­те код с ми­ни­маль­ным чис­ло­вым зна­че­ни­ем.

При­ме­ча­ние. Усло­вие Фано озна­ча­ет, что ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова.

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

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

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

а)  если число N крат­но 3, тогда в конец до­пи­сы­ва­ет­ся три млад­ших раз­ря­да по­лу­чен­ной дво­ич­ной за­пи­си;

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

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

На­при­мер, для ис­ход­но­го числа 5₁₀  =  101₂ ре­зуль­та­том яв­ля­ет­ся число 101110₂  =  46₁₀, а для ис­ход­но­го числа 9₁₀  =  1001₂ ре­зуль­та­том яв­ля­ет­ся число 1001001₂  =  73₁₀.

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

Ис­пол­ни­тель Че­ре­па­ха пе­ре­дви­га­ет­ся по плос­ко­сти и остав­ля­ет след в виде линии. Че­ре­па­ха может вы­пол­нять три ко­ман­ды.

По ко­ман­де Вперёд n Че­ре­па­ха пе­ре­ме­ща­ет­ся вперёд на n еди­ниц.

По ко­ман­де На­пра­во m Че­ре­па­ха по­во­ра­чи­ва­ет­ся на месте на m гра­ду­сов по ча­со­вой стрел­ке, при этом со­от­вет­ствен­но ме­ня­ет­ся на­прав­ле­ние даль­ней­ше­го дви­же­ния.

По ко­ман­де На­ле­во m Че­ре­па­ха по­во­ра­чи­ва­ет­ся на месте на m гра­ду­сов про­тив ча­со­вой стрел­ки, при этом со­от­вет­ствен­но ме­ня­ет­ся на­прав­ле­ние даль­ней­ше­го дви­же­ния.

В на­чаль­ный мо­мент Че­ре­па­ха на­хо­дит­ся в на­ча­ле ко­ор­ди­нат и на­прав­ле­на вверх (вдоль по­ло­жи­тель­но­го на­прав­ле­ния оси ор­ди­нат), хвост опу­щен.

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

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

На­пра­во 315

По­вто­ри 7 [Вперёд 16 На­пра­во 45 Вперёд 8 На­пра­во 135].

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

Го­ло­со­вое со­об­ще­ние, за­пи­сан­ное в сте­рео фор­ма­те, пе­ре­да­ет­ся со ско­ро­стью 64 000 бит/⁠с. Файл был за­пи­сан с та­ки­ми па­ра­мет­ра­ми: глу­би­на ко­ди­ро­ва­ния  — 24 бит на от­счет, ча­сто­та дис­кре­ти­за­ции  — 16 000 от­сче­тов в се­кун­ду, время за­пи­си   — 90 с. Сколь­ко се­кунд будет пе­ре­да­вать­ся го­ло­со­вое со­об­ще­ние?

Все че­ты­рех­бук­вен­ные слова, в со­ста­ве ко­то­рых могут быть толь­ко рус­ские буквы А, В, Л, О, Р за­пи­са­ны в ал­фа­вит­ном по­ряд­ке и про­ну­ме­ро­ва­ны на­чи­ная с 1.

Ниже при­ве­де­но на­ча­ло спис­ка.

1.  АААА

2.  АААВ

3.  АААЛ

4.  АААО

5.  АААР

6.  ААВА

...

Под каким но­ме­ром идет пер­вое слово, на­чи­на­ю­ще­е­ся на Л?

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

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

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

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

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

Текст по­ве­сти Алек­сандра Куп­ри­на «По­еди­нок» пред­став­лен в виде фай­лов раз­лич­ных фор­ма­тов. От­крой­те один из фай­лов и опре­де­ли­те, сколь­ко раз в тек­сте встре­ча­ют­ся ком­би­на­ция сим­во­лов «Час» или «час», не яв­ля­ю­щи­е­ся от­дель­ны­ми сло­ва­ми.

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

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

Опре­де­ли­те объём па­мя­ти (в Кбайт), не­об­хо­ди­мый для хра­не­ния 32 768 иден­ти­фи­ка­то­ров.

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

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

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

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

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

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

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

Цикл

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

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

КОНЕЦ ПОКА

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

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

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

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

КОНЕЦ ЕСЛИ

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

Ис­пол­ни­тель Ре­дак­тор по­лу­ча­ет на вход стро­ку, на­чи­на­ю­щу­ю­ся на 3 и со­дер­жа­щую далее n пя­те­рок (5), где n > 3.

На вы­пол­не­ние Ре­дак­то­ру дана сле­ду­ю­щая про­грам­ма:

НА­ЧА­ЛО

ПОКА на­шлось (25) ИЛИ на­шлось (355) ИЛИ на­шлось (555)

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

                    ТО за­ме­нить (25, 3)

                 КОНЕЦ ЕСЛИ

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

                      ТО за­ме­нить (355, 52)

                 КОНЕЦ ЕСЛИ

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

                       ТО за­ме­нить (555, 23)

                 КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Най­ди­те ми­ни­маль­ное зна­че­ние n, при ко­то­ром сумма цифр ко­неч­ной стро­ки будет равна 27.

На ри­сун­ке пред­став­ле­на схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Опре­де­ли­те ко­ли­че­ство раз­лич­ных путей, ко­то­рые на­чи­на­ют­ся в го­ро­де А и за­кан­чи­ва­ют­ся в го­ро­де М.

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

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

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

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

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

F(n)  =  n, если n ≥ 2025;

F(n)  =  n + 3 + F(n + 3), если n < 2025.

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

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

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

Ответ:

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

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

При­мер вход­ных дан­ных:

Для дан­ных из при­ме­ра ответ 34 22.

Ответ:

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

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

Ис­пол­ни­тель Ал­ле­гро пре­об­ра­зу­ет число на экра­не.

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

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

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

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

Пер­вая ко­ман­да уве­ли­чи­ва­ет число на экра­не на 1, вто­рая уве­ли­чи­ва­ет число на

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

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

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

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

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

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

В аэро­пор­ту есть ка­ме­ра хра­не­ния из K ячеек, ко­то­рые про­ну­ме­ро­ва­ны с 1.

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

Най­ди­те ко­ли­че­ство ба­га­жей, ко­то­рое будет сдано в ка­ме­ры за 24 часа и номер ячей­ки, в ко­то­рую сдаст багаж по­след­ний пас­са­жир.

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

В пер­вой стро­ке вход­но­го файла на­хо­дит­ся число K  — ко­ли­че­ство ячеек в ка­ме­ре хра­не­ния, во вто­рой стро­ке файла число N  — ко­ли­че­ство пас­са­жи­ров, сда­ю­щих багаж (на­ту­раль­ное число, не пре­вы­ша­ю­щее 1000). Каж­дая из сле­ду­ю­щих N строк со­дер­жит два на­ту­раль­ных числа, не пре­вы­ша­ю­щих 1440: время сдачи ба­га­жа и время вы­да­чи ба­га­жа.

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

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

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

2

4

30 1000

60 100

61 1100

1010 1440

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

Ответ:

Ме­тео­ро­ло­ги­че­ская стан­ция ведёт на­блю­де­ние за ко­ли­че­ством вы­пав­ших осад­ков. По­ка­за­ния за­пи­сы­ва­ют­ся каж­дую ми­ну­ту в те­че­ние N минут.

Опре­де­ля­ет­ся пара из­ме­ре­ний, между ко­то­ры­ми про­шло не менее K минут. Най­ди­те мак­си­маль­ную сумму по­ка­за­ний среди таких пар.

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

Даны два вход­ных файла (A и B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит число N  — ко­ли­че­ство из­ме­ре­ний, во вто­рой стро­ке K  — ми­ни­маль­ное ко­ли­че­ство минут между ис­ко­мы­ми из­ме­ре­ни­я­ми. В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся число: ко­ли­че­ство вы­пав­ших осад­ков.

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

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

Ответ: