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

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

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

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

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

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

При­мер. Пусть за­да­ны вы­ра­же­ние x → y, за­ви­ся­щее от двух пе­ре­мен­ных x и y, и фраг­мент таб­ли­цы ис­тин­но­сти.

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

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

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

Ис­поль­зуя ин­фор­ма­цию из при­ведённой базы дан­ных, опре­де­ли­те ма­га­зин, по­лу­чив­ший наи­боль­шую общую сумму вы­руч­ки от про­даж то­ва­ров от­де­ла «Мо­ло­ко» с 10 по 12 июня.

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

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

Белый  — 0, Зелёный  — 11111, Фи­о­ле­то­вый  — 11110, Крас­ный  — 1110, Чёрный  — 10. Ука­жи­те крат­чай­шее ко­до­вое слово для ко­ди­ро­ва­ния си­не­го цвета, при ко­то­ром код будет до­пус­кать од­но­знач­ное де­ко­ди­ро­ва­ние.

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

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

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

2.  В конец дво­ич­ной за­пи­си до­бав­ля­ют­ся две пер­вые цифры этой за­пи­си в об­рат­ном по­ряд­ке.

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

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

1.  Дво­ич­ная за­пись числа N: 1011.

2.  В конец за­пи­си до­бав­ля­ют­ся цифры 01  — пер­вые две цифры в об­рат­ном по­ряд­ке (сна­ча­ла вто­рая, затем пер­вая), по­лу­ча­ет­ся 101101.

3.  На экран вы­во­дит­ся число 45.

При каком наи­мень­шем ис­ход­ном N ре­зуль­тат на экра­не ав­то­ма­та будет боль­ше 90?

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

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

Ка­ме­ра до­рож­но­го на­блю­де­ния де­ла­ет цвет­ные фо­то­гра­фии с раз­ре­ше­ни­ем пик­се­лей, ис­поль­зуя па­лит­ру из 4096 цве­тов. Сним­ки со­хра­ня­ют­ся в па­мя­ти ка­ме­ры, груп­пи­ру­ют­ся в па­ке­ты по 100 штук и от­прав­ля­ют­ся в центр об­ра­бот­ки по ка­на­лу связи с про­пуск­ной спо­соб­но­стью 128 Кбайт/сек. На сколь­ко про­цен­тов не­об­хо­ди­мо сжать изоб­ра­же­ния, чтобы пе­ре­да­вать один пакет за 6 минут? За­го­лов­ки и дру­гую слу­жеб­ную ин­фор­ма­цию не учи­ты­вать. В от­ве­те за­пи­ши­те число  — округлённый до це­ло­го про­цент сжа­тия. Знак про­цен­та пи­сать не нужно.

Уче­ни­ца со­став­ля­ет 5-⁠бук­вен­ные слова из букв ГЕ­ПАРД. При этом в каж­дом слове ровно одна буква Г, слово не может на­чи­нать­ся на букву А и за­кан­чи­вать­ся бук­вой Е. Какое ко­ли­че­ство слов может со­ста­вить уче­ни­ца?

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

Назовём ячей­ку таб­ли­цы ин­те­рес­ной, если вы­пол­ня­ют­ся сле­ду­ю­щие усло­вия:

—  число в дан­ной ячей­ке боль­ше не встре­ча­ет­ся в дан­ной стро­ке;

—  в со­сед­них ячей­ках есть хотя бы одно число, боль­шее, чем число в дан­ной ячей­ке.

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

—  стро­ка со­дер­жит не менее трёх ин­те­рес­ных ячеек;

—  в стро­ке есть по­вто­ря­ю­щи­е­ся числа.

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

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 14 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы Е, Г, Э, 2, 0, 1, 4. Каж­дый такой па­роль в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством байт (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит).

Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 30 па­ро­лей. (Ответ дайте в бай­тах.)

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

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

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

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

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

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

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

НА­ЧА­ЛО

                ПОКА НЕ на­шлось (00)

                        за­ме­нить (033, 1302)

                        за­ме­нить (03, 120)

                        за­ме­нить (023, 203)

                        за­ме­нить (02, 20)

                КОНЕЦ ПОКА

КОНЕЦ

Из­вест­но, что в ис­ход­ной стро­ке A было ровно два нуля  — на пер­вом и на по­след­нем месте, а после вы­пол­не­ния дан­ной про­грам­мы по­лу­чи­лась стро­ка B, со­дер­жа­щая 333 еди­ни­цы, 819 двоек и 181 трой­ку. Какое наи­боль­шее ко­ли­че­ство двоек могло быть в стро­ке A?

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

По за­дан­ным IP-⁠ад­ре­су узла и маске опре­де­ли­те адрес сети.

IP-⁠адрес узла: 218.137.218.137

Маска: 255.255.248.0

При за­пи­си от­ве­та вы­бе­ри­те из при­ведённых в таб­ли­це чисел че­ты­ре эле­мен­та IP-⁠ад­ре­са и за­пи­ши­те в нуж­ном по­ряд­ке со­от­вет­ству­ю­щие им буквы без ис­поль­зо­ва­ния точек.

При­мер.

Пусть ис­ко­мый адрес сети 192.168.128.0 и дана таб­ли­ца:

В этом слу­чае пра­виль­ный ответ будет HBAF.

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

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

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

Для ка­ко­го наи­боль­ше­го на­ту­раль­но­го числа А ло­ги­че­ское вы­ра­же­ние тож­де­ствен­но ис­тин­на (то есть при­ни­ма­ет зна­че­ние 1 при любом на­ту­раль­ном зна­че­нии пе­ре­мен­ной x), если B  =  [70, 90]?

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

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

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

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

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

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

—  в трой­ке есть хотя бы два четырёхзнач­ных числа;

—  в трой­ке есть число, по­след­няя цифра ко­то­ро­го сов­па­да­ет с по­след­ней циф­рой мак­си­маль­но­го эле­мен­та всей по­сле­до­ва­тель­но­сти;

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

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

Ответ:

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

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

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

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

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

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

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

Ответ:

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

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

По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 42 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней; 1 ≤ S ≤ 41.

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

встре­тить­ся при раз­лич­ной игре про­тив­ни­ка.

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

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

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

По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 42 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней; 1 ≤ S ≤ 41.

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

встре­тить­ся при раз­лич­ной игре про­тив­ни­ка.

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

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

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

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

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

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

По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 42 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней; 1 ≤ S ≤ 41.

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

встре­тить­ся при раз­лич­ной игре про­тив­ни­ка.

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

Пер­вая из них уве­ли­чи­ва­ет на 1 число на экра­не, вто­рая уве­ли­чи­ва­ет это число в 2 раза, тре­тья  — в 3 раза.

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

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов араб­ских цифр (0, 1, ..., 9). Опре­де­ли­те мак­си­маль­ное ко­ли­че­ство иду­щих под­ряд цифр, среди ко­то­рых каж­дые две со­сед­ние раз­лич­ны.

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

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

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

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

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

5

43

40

32

40

30

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

При таких ис­ход­ных дан­ных усло­вию за­да­чи удо­вле­тво­ря­ют на­бо­ры кор­жей с диа­мет­ра­ми 30, 40 и 43 или 32, 40 и 43 со­от­вет­ствен­но, то есть ко­ли­че­ство кор­жей равно 3, а мак­си­маль­но воз­мож­ный диа­метр са­мо­го ма­лень­ко­го коржа равен 32.

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

Ответ:

Пусть 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.

Ответ: