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

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

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

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

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

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

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

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

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

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

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

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

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

2.  Под­счи­ты­ва­ет­ся ко­ли­че­ство чётных и нечётных цифр в де­ся­тич­ной за­пи­си за­дан­но­го числа. Если в де­ся­тич­ной за­пи­си боль­ше чётных цифр, то в конец дво­ич­ной за­пи­си до­пи­сы­ва­ет­ся 1, если нечётных  — 0. Если чётных и нечётных цифр в де­ся­тич­ной за­пи­си по­ров­ну, то в конец дво­ич­ной за­пи­си до­пи­сы­ва­ет­ся 0, если дан­ное число чётное, и 1  — если нечётное.

3−4.  Пункт 2 по­вто­ря­ет­ся для вновь по­лу­чен­ных чисел ещё два раза.

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

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

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

2.  В за­пи­си числа 14 чётных и нечётных цифр по­ров­ну. Число 14 чётное, до­пи­сы­ва­ем к дво­ич­ной за­пи­си 0, по­лу­ча­ем 11100₂  =  28₁₀.

3.  В за­пи­си числа 28 чётных цифр боль­ше, до­пи­сы­ва­ем к дво­ич­ной за­пи­си 1, по­лу­ча­ем 111001₂  =  57₁₀.

4.  В за­пи­си числа 57 нечётных цифр боль­ше, до­пи­сы­ва­ем к дво­ич­ной за­пи­си 0, по­лу­ча­ем 1110010₂  =  114₁₀.

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

Опре­де­ли­те ко­ли­че­ство при­над­ле­жа­щих от­рез­ку [123 455; 987 654 321] чисел, ко­то­рые могут по­лу­чить­ся в ре­зуль­та­те ра­бо­ты этого ал­го­рит­ма.

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

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

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

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

Ав­то­ма­ти­че­ская ка­ме­ра про­из­во­дит раст­ро­вые изоб­ра­же­ния раз­ме­ром 600 на 1000 пик­се­лей. Для ко­ди­ро­ва­ния цвета каж­до­го пик­се­ля ис­поль­зу­ет­ся оди­на­ко­вое ко­ли­че­ство бит, коды пик­се­лей за­пи­сы­ва­ют­ся в файл один за дру­гим без про­ме­жут­ков. Объём файла с изоб­ра­же­ни­ем не может пре­вы­шать 250 Кбайт без учёта раз­ме­ра за­го­лов­ка файла. Какое мак­си­маль­ное ко­ли­че­ство цве­тов можно ис­поль­зо­вать в па­лит­ре?

Все 5-⁠бук­вен­ные слова, со­став­лен­ные из букв А, О, У, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке. Вот на­ча­ло спис­ка:

1.  ААААА

2.  ААААО

3.  ААААУ

4.  АААОА

...

Ука­жи­те номер слова УАУАУ.

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

Опре­де­ли­те, сколь­ко раз в тек­сте поэмы Н. А. Не­кра­со­ва «Кому на Руси жить хо­ро­шо» встре­ча­ет­ся слово «Мой» на­пи­сан­ное с про­пис­ной буквы. Дру­гие формы слова «Мой», такие как «Мои», «Моего» и про­чие, учи­ты­вать не сле­ду­ет.

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

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

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

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

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

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

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

Цикл

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

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

КОНЕЦ ПОКА

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

Най­ди­те сумму цифр в стро­ке, ко­то­рая по­лу­чит­ся в ре­зуль­та­те при­ме­не­ния при­ведённой ниже про­грам­мы к стро­ке, со­сто­я­щей из 65 цифр 9.

НА­ЧА­ЛО

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

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

            ТО за­ме­нить (222, 9)

        ИНАЧЕ

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

        КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

КОНЕЦ

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

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

На­при­мер, если IP-⁠адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-⁠ад­ре­сом 93.138.161.94 адрес сети равен 93.138.160.0. Какое наи­боль­шее ко­ли­че­ство нулей может быть в дво­ич­ной за­пи­си маски?

Зна­че­ние вы­ра­же­ния 4¹⁶ + 2³⁴ − 8 за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 2. Сколь­ко цифр 1 со­дер­жит­ся в этой за­пи­си?

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

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

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

F(1)  =  1;

F(2)  =  1;

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

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

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

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

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

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

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

Ответ:

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

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

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

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

В от­ве­те ука­жи­те два числа: сна­ча­ла мак­си­маль­ную сумму, затем ми­ни­маль­ную.

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

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

Ответ:

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может: до­ба­вить в кучу один ка­мень (дей­ствие А) или утро­ить ко­ли­че­ство кам­ней в куче, а затем до­ба­вить ещё один ка­мень (дей­ствие Б). На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11 или 31 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся более 31. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 32 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 31.

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может: до­ба­вить в кучу один ка­мень (дей­ствие А) или утро­ить ко­ли­че­ство кам­ней в куче, а затем до­ба­вить ещё один ка­мень (дей­ствие Б). На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11 или 31 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся более 31. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 32 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 31.

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

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

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

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может: до­ба­вить в кучу один ка­мень (дей­ствие А) или утро­ить ко­ли­че­ство кам­ней в куче, а затем до­ба­вить ещё один ка­мень (дей­ствие Б). На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11 или 31 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся более 31. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 32 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней; 1 ≤ S ≤ 31.

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

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

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

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

Про­грам­ма для ис­пол­ни­те­ля  — это по­сле­до­ва­тель­ность ко­манд. На­при­мер, если в на­чаль­ный мо­мент на экра­не на­хо­дит­ся число 1, то про­грам­ма 213 по­сле­до­ва­тель­но пре­об­ра­зу­ет его в 3, 4, 8.

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

Тек­сто­вый файл со­сто­ит из цифр от 1 до 9, зна­ков опе­ра­ций «+», «–» и «*» (сло­же­ние, вы­чи­та­ние и умно­же­ние) и за­глав­ных ла­тин­ских букв A, B, C, D.

Назовём пра­виль­ной сум­мой стро­ку, со­дер­жа­щую по­сле­до­ва­тель­ность из од­но­го или более де­ся­тич­ных чисел, в ко­то­рой между со­сед­ни­ми чис­ла­ми стоит ровно один знак «+» или «–» и нет дру­гих зна­ков.

При­ме­ры пра­виль­ных сумм: «23», «115+6», «1980+12−123−51+3».

Назовём ре­зуль­та­том пра­виль­ной суммы число, ко­то­рое по­лу­чит­ся при вы­пол­не­нии за­пи­сан­ных в со­от­вет­ству­ю­щей стро­ке сло­же­ний. На­при­мер, ре­зуль­тат пра­виль­ной суммы «2+3»  — число 5, а ре­зуль­тат пра­виль­ной суммы «1+2−8+3»  — число −2.

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

В от­ве­те за­пи­ши­те ре­зуль­тат най­ден­ной суммы. Га­ран­ти­ру­ет­ся, что ответ не пре­вы­ша­ет 2 · 10⁹.

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

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

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

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

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

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

Ответ:

По ка­на­лу связи пе­ре­даётся по­сле­до­ва­тель­ность целых чисел  — по­ка­за­ния при­бо­ра. В те­че­ние 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  — это сумма зна­че­ний, за­фик­си­ро­ван­ных на пер­вой, тре­тьей и ше­стой ми­ну­тах из­ме­ре­ний.

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

Ответ: