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

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

Ло­ги­че­ская функ­ция F задаётся вы­ра­же­ни­ем (x ∧ ¬y) ∨ (y ≡ z ) ∨ w.

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

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

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

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

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко семь букв: А, Б, И, К, Л, О, С. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: А  — 001, И  — 01, С  — 10. Какое наи­мень­шее ко­ли­че­ство дво­ич­ных зна­ков по­тре­бу­ет­ся для ко­ди­ро­ва­ния слова КО­ЛО­БОК?

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

Ав­то­мат об­ра­ба­ты­ва­ет на­ту­раль­ное число N (0 ≤ N ≤ 255) по сле­ду­ю­ще­му ал­го­рит­му.

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

2.  Все цифры дво­ич­ной за­пи­си за­ме­ня­ют­ся на про­ти­во­по­лож­ные (0 на 1, 1 на 0).

3.  По­лу­чен­ное число пе­ре­во­дит­ся в де­ся­тич­ную за­пись.

4.  Из но­во­го числа вы­чи­та­ет­ся ис­ход­ное, по­лу­чен­ная раз­ность вы­во­дит­ся на экран.

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

1.  Вось­ми­бит­ная дво­ич­ная за­пись числа N: 00001101.

2.  Все цифры за­ме­ня­ют­ся на про­ти­во­по­лож­ные, новая за­пись: 11110010.

3.  Де­ся­тич­ное зна­че­ние по­лу­чен­но­го числа 242.

4.  На экран вы­во­дит­ся число 242 − 13  =  229.

Какое число нужно вве­сти в ав­то­мат, чтобы в ре­зуль­та­те по­лу­чи­лось 133?

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

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

Для хра­не­ния про­из­воль­но­го раст­ро­во­го изоб­ра­же­ния раз­ме­ром 1024 × 1024 пик­се­лей от­ве­де­но 512 Кбайт па­мя­ти, при этом для каж­до­го пик­се­ля хра­нит­ся дво­ич­ное число  — код цвета этого пик­се­ля. Для каж­до­го пик­се­ля для хра­не­ния кода вы­де­ле­но оди­на­ко­вое ко­ли­че­ство бит. Сжа­тие дан­ных не про­из­во­дит­ся. Какое мак­си­маль­ное ко­ли­че­ство цве­тов можно ис­поль­зо­вать в изоб­ра­же­нии?

Сколь­ко слов длины 5, на­чи­на­ю­щих­ся с глас­ной буквы, можно со­ста­вить из букв Е, Г, Э? Каж­дая буква может вхо­дить в слово не­сколь­ко раз. Слова не обя­за­тель­но долж­ны быть осмыс­лен­ны­ми сло­ва­ми рус­ско­го языка.

В файле на­хо­дит­ся таб­ли­ца, ко­то­рая со­дер­жит в каж­дой из строк по 7 на­ту­раль­ных чисел. Най­ди­те ко­ли­че­ство таких строк, в ко­то­рых два числа по­вто­ря­ют­ся по 2 раза, а 3 дру­гих раз­лич­ны, сред­нее ариф­ме­ти­че­ское не­по­вто­ря­ю­щих­ся чисел мень­ше сред­не­го ариф­ме­ти­че­ско­го по­вто­ря­ю­щих­ся.

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

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 15 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы из 12-⁠сим­воль­но­го на­бо­ра: А, В, C, D, Е, F, G, H, К, L, M, N. В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Кроме соб­ствен­но па­ро­ля, для каж­до­го поль­зо­ва­те­ля в си­сте­ме хра­нят­ся до­пол­ни­тель­ные све­де­ния, для чего от­ве­де­но 12 байт на од­но­го поль­зо­ва­те­ля.

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

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

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

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

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

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

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

Цикл

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

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

КОНЕЦ ПОКА

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

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

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

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

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

КОНЕЦ ЕСЛИ

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

Какая стро­ка по­лу­чит­ся в ре­зуль­та­те при­ме­не­ния при­ведённой ниже про­грам­мы к стро­ке, со­сто­я­щей из 77 еди­ниц?

НА­ЧА­ЛО

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

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

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

            ИНАЧЕ за­ме­нить (11, 2)

        КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

КОНЕЦ

Мас­кой под­се­ти на­зы­ва­ет­ся 32-⁠раз­ряд­ное дво­ич­ное число, ко­то­рое опре­де­ля­ет, какая часть IP-⁠ад­ре­са ком­пью­те­ра от­но­сит­ся к ад­ре­су сети, а какая часть IP-⁠ад­ре­са опре­де­ля­ет адрес ком­пью­те­ра в под­се­ти. В маске под­се­ти стар­шие биты, от­ве­ден­ные в IP-⁠ад­ре­се ком­пью­те­ра для ад­ре­са сети, имеют зна­че­ние 1; млад­шие биты, от­ве­ден­ные в IP-⁠ад­ре­се ком­пью­те­ра для ад­ре­са ком­пью­те­ра в под­се­ти, имеют зна­че­ние 0.

Если маска под­се­ти 255.255.255.224 и IP-⁠адрес ком­пью­те­ра в сети 162.198.0.157, то по­ряд­ко­вый номер ком­пью­те­ра в сети равен _____.

Сколь­ко еди­ниц со­дер­жит­ся в дво­ич­ной за­пи­си зна­че­ния вы­ра­же­ния: 4²⁵⁵ + 2²⁵⁵ − 255?

На чис­ло­вой пря­мой даны два от­рез­ка: P  =  [25; 50] и Q  =  [32; 47]. Ука­жи­те наи­боль­шую воз­мож­ную длину про­ме­жут­ка A, для ко­то­ро­го фор­му­ла

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

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

F(1)  =  1;

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

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

В файле со­дер­жит­ся по­сле­до­ва­тель­ность из 10 000 целых по­ло­жи­тель­ных чисел. Каж­дое число не пре­вы­ша­ет 10 000. Опре­де­ли­те и за­пи­ши­те в от­ве­те сна­ча­ла ко­ли­че­ство пар эле­мен­тов по­сле­до­ва­тель­но­сти, у ко­то­рых сумма нечётна, а про­из­ве­де­ние де­лит­ся на 3, затем мак­си­маль­ную из сумм эле­мен­тов таких пар. В дан­ной за­да­че под парой под­ра­зу­ме­ва­ет­ся два раз­лич­ных эле­мен­та по­сле­до­ва­тель­но­сти. По­ря­док эле­мен­тов в паре не важен.

Ответ:

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

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

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

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

Для ука­зан­ных вход­ных дан­ных от­ве­том долж­на быть пара чисел 41 и 22.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В таб­ли­це пред­став­ле­ны иден­ти­фи­ка­тор (ID) каж­до­го про­цес­са, его дли­тель­ность, для за­ви­си­мых про­цес­сов  — ID по­став­щи­ков дан­ных. Для не­за­ви­си­мых про­цес­сов в ка­че­стве ID по­став­щи­ков дан­ных ука­зан 0. Опре­де­ли­те мак­си­маль­ную дли­тель­ность от­рез­ка вре­ме­ни (в мс), в те­че­ние ко­то­ро­го воз­мож­но од­но­вре­мен­ное вы­пол­не­ние четырёх про­цес­сов, при усло­вии, что в эту четвёрку не вхо­дит про­цесс с ID  =  2.

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

Ис­пол­ни­тель Раз­Два пре­об­ра­зу­ет число на экра­не. У ис­пол­ни­те­ля есть две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

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

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

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

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов A, B и C. Опре­де­ли­те мак­си­маль­ное ко­ли­че­ство иду­щих под­ряд сим­во­лов, среди ко­то­рых каж­дые два со­сед­них раз­лич­ны.

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

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

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

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

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

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

При­мер вход­но­го файла:

100 4

80

30

50

40

При таких ис­ход­ных дан­ных можно со­хра­нить файлы мак­си­мум двух поль­зо­ва­те­лей. Воз­мож­ные объёмы этих двух фай­лов  — 30 и 40, 30 и 50 или 40 и 50. Наи­боль­ший объём файла из пе­ре­чис­лен­ных пар  — 50, по­это­му ответ для при­ведённого при­ме­ра:

2 50

Ответ:

По­сле­до­ва­тель­ность на­ту­раль­ных чисел ха­рак­те­ри­зу­ет­ся чис­лом Х  — наи­боль­шим чис­лом, крат­ным 14 и яв­ля­ю­щим­ся про­из­ве­де­ни­ем двух эле­мен­тов по­сле­до­ва­тель­но­сти с раз­лич­ны­ми но­ме­ра­ми. Га­ран­ти­ру­ет­ся, что хотя бы одно такое про­из­ве­де­ние в по­сле­до­ва­тель­но­сти есть.

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых со­дер­жит в пер­вой стро­ке ко­ли­че­ство чисел N (1 ≤ N ≤ 100 000). В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 1000.

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

5

40

1000

7

28

55

При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных:

28000 В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мо­го про­из­ве­де­ния для файла А, затем для файла B.

Ответ: