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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей толь­ко из букв А, Б, В, Г, Д, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для букв А, Б, В ис­поль­зо­ва­ли со­от­вет­ствен­но ко­до­вые слова 1, 00, 0100. Ука­жи­те ми­ни­маль­ную воз­мож­ную сум­мар­ную длину для букв Г и Д, если из­вест­но, что код дол­жен до­пус­кать од­но­знач­ное де­ко­ди­ро­ва­ние.

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

Ав­то­мат по­лу­ча­ет на вход четырёхзнач­ное число. По этому числу стро­ит­ся новое число по сле­ду­ю­щим пра­ви­лам.

1.  Скла­ды­ва­ют­ся от­дель­но пер­вая и вто­рая цифры, вто­рая и тре­тья цифры, а также тре­тья и четвёртая цифры.

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

При­мер. Ис­ход­ное число: 9575. Суммы: 9 + 5  =  14; 5 + 7  =  12; 7 + 5  =  12. Наи­боль­шие суммы: 14, 12. Ре­зуль­тат: 1214.

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

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

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

Изоб­ра­же­ние раз­ме­ром 315 × 3072 пик­се­лей со­хра­ня­ет­ся в па­мя­ти ком­пью­те­ра. Для его хра­не­ния вы­де­ля­ет­ся не более 735 Кбайт без учёта за­го­лов­ка файла. Все пик­се­ли ко­ди­ру­ют­ся оди­на­ко­вым ко­ли­че­ством бит и за­пи­сы­ва­ют­ся в файл один за дру­гим. Какое мак­си­маль­ное ко­ли­че­ство цве­тов можно ис­поль­зо­вать в изоб­ра­же­нии? В от­ве­те за­пи­ши­те толь­ко число.

Все 4-⁠бук­вен­ные слова, со­став­лен­ные из букв В, Л, Т, У, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке и про­ну­ме­ро­ва­ны.

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

1.  ВВВВ

2.  ВВВЛ

3.  ВВВТ

4.  ВВВУ

...

За­пи­ши­те слово, ко­то­рое стоит под но­ме­ром 98.

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

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

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

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

По­весть бра­тьев Стру­гац­ких «По­не­дель­ник на­чи­на­ет­ся в суб­бо­ту» со­сто­ит из трёх ис­то­рий. Опре­де­ли­те, сколь­ко раз во вто­рой ис­то­рии, вклю­чая за­го­лов­ки, эпи­гра­фы и снос­ки, встре­ча­ют­ся слова из трёх букв, вклю­чая трёхбук­вен­ные со­кра­ще­ния и аб­бре­ви­а­ту­ры. В этом за­да­нии части слова, раз­делённые де­фи­сом, рас­смат­ри­ва­ют­ся как от­дель­ные слова. На­при­мер, слово «кто-то» учи­ты­ва­ет­ся как два от­дель­ных слова: трёхбук­вен­ное и двух­бук­вен­ное.

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 16 сим­во­лов и со­дер­жа­щий толь­ко за­глав­ные сим­во­лы сред­не­го ряда ла­тин­ской рас­клад­ки кла­ви­а­ту­ры: A, S, D, F, G, H, J, K, L. Каж­дый такой па­роль в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством байт (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит). Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 20 па­ро­лей. (Ответ дайте в бай­тах.)

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

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

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

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

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

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

ис­пол­ни­те­ля при этом не из­ме­ня­ет­ся.

Цикл

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

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

    КОНЕЦ ПОКА

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

НА­ЧА­ЛО

    ПОКА на­шлось (1111)

        за­ме­нить (1111, 22)

        за­ме­нить (222, 1)

    КОНЕЦ ПОКА

КОНЕЦ

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

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

Адрес сети по­лу­ча­ет­ся в ре­зуль­та­те при­ме­не­ния по­раз­ряд­ной конъ­юнк­ции к за­дан­но­му IP-⁠ад­ре­су узла и маске.

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

Узлы с IP-⁠ад­ре­са­ми 202.3.20.24 и 202.3.27.11 на­хо­дят­ся в одной сети. Ука­жи­те наи­мень­шее воз­мож­ное ко­ли­че­ство при­над­ле­жа­щих этой сети IP-⁠ад­ре­сов, в дво­ич­ной за­пи­си ко­то­рых чётное число еди­ниц.

В си­сте­ме счис­ле­ния с ос­но­ва­ни­ем p вы­пол­ня­ет­ся ра­вен­ство 32x8 + xxx9  =  yy02. Бук­ва­ми x и y обо­зна­че­ны не­ко­то­рые цифры из ал­фа­ви­та си­сте­мы счис­ле­ния с ос­но­ва­ни­ем p. Опре­де­ли­те зна­че­ние числа yyx_p и за­пи­ши­те это зна­че­ние в де­ся­тич­ной си­сте­ме счис­ле­ния.

На чис­ло­вой пря­мой даны два от­рез­ка: Р  =  [22, 72] и Q  =  [42, 102]. Ка­ко­ва наи­мень­шая воз­мож­ная длина ин­тер­ва­ла A, что ло­ги­че­ское вы­ра­же­ние

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

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

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

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

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

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

Ответ:

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

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

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

Ответ:

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 5 кам­ней, а в дру­гой  — 9 кам­ней; такую по­зи­цию мы будем обо­зна­чать (5, 9). За один ход из по­зи­ции (5, 9) можно по­лу­чить любую из четырёх по­зи­ций: (6, 9), (10, 9), (5, 10), (5, 18).

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

В на­чаль­ный мо­мент в пер­вой куче было 8 кам­ней, во вто­рой куче  — S кам­ней; 1 ≤ S ≤ 68.

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 5 кам­ней, а в дру­гой  — 9 кам­ней; такую по­зи­цию мы будем обо­зна­чать (5, 9). За один ход из по­зи­ции (5, 9) можно по­лу­чить любую из четырёх по­зи­ций: (6, 9), (10, 9), (5, 10), (5, 18).

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

В на­чаль­ный мо­мент в пер­вой куче было 8 кам­ней, во вто­рой куче  — S кам­ней; 1 ≤ S ≤ 68.

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

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

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

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 5 кам­ней, а в дру­гой  — 9 кам­ней; такую по­зи­цию мы будем обо­зна­чать (5, 9). За один ход из по­зи­ции (5, 9) можно по­лу­чить любую из четырёх по­зи­ций: (6, 9), (10, 9), (5, 10), (5, 18).

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

В на­чаль­ный мо­мент в пер­вой куче было 8 кам­ней, во вто­рой куче  — S кам­ней; 1 ≤ S ≤ 68.

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

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

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

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов ла­тин­ско­го ал­фа­ви­та. Опре­де­ли­те ми­ни­маль­ную под­стро­ку, со­дер­жа­щую 210 сим­во­лов T. Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му.

При про­ве­де­нии экс­пе­ри­мен­та за­ря­жен­ные ча­сти­цы по­па­да­ют на чув­стви­тель­ный экран, пред­став­ля­ю­щий из себя мат­ри­цу раз­ме­ром 100 000 на 100 000 точек. При по­па­да­нии каж­дой ча­сти­цы на экран в про­то­ко­ле фик­си­ру­ют­ся ко­ор­ди­на­ты по­па­да­ния: номер ряда (целое число от 1 до 100 000) и номер по­зи­ции в ряду (целое число от 1 до 100 000).

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

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

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

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

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

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

Ответ:

Для участ­ни­ков ве­ло­гон­ки на каж­дом ки­ло­мет­ре коль­це­вой трас­сы с дву­сто­рон­ним дви­же­ни­ем уста­нов­ле­ны пунк­ты пи­та­ния. Длина коль­це­вой трас­сы равна N ки­ло­мет­ров. Ну­ле­вой и N-⁠й ки­ло­мет­ры трас­сы на­хо­дят­ся в одной точке. Из­вест­но ко­ли­че­ство ком­плек­тов пи­та­ния в каж­дом из пунк­тов на трас­се. В каж­дый пункт ком­плек­ты пи­та­ния до­став­ля­ет от­дель­ный элек­тро­кар. Сто­и­мость до­став­ки пи­та­ния вы­чис­ля­ет­ся как про­из­ве­де­ние ко­ли­че­ства ком­плек­тов пи­та­ния на рас­сто­я­ние от мо­биль­но­го цеха их под­го­тов­ки до пунк­та пи­та­ния спортс­ме­нов на трас­се. Мо­биль­ный цех под­го­тов­ки ком­плек­тов рас­по­ло­жен в одном из пунк­тов пи­та­ния на трас­се таким об­ра­зом, что общая сто­и­мость до­став­ки из цеха во все пунк­ты ми­ни­маль­на.

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

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

Дано два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит число N (1 ≤ N ≤ 10 000 000)  — ко­ли­че­ство

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

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

6

8

20

5

13

7

19

При таких ис­ход­ных дан­ных, если кон­тей­не­ры уста­нов­ле­ны на каж­дом ки­ло­мет­ре ав­то­до­ро­ги, не­об­хо­ди­мо от­крыть центр пе­ре­ра­бот­ки в пунк­те 6. В этом слу­чае сумма транс­порт­ных за­трат со­ста­вит: 1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.

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

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

Ответ: