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

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

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

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

Но успел за­пол­нить лишь фраг­мент из трех раз­лич­ных её строк, даже не ука­зав, ка­ко­му столб­цу таб­ли­цы со­от­вет­ству­ет каж­дая пе­ре­мен­ная x, y, z, w.

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

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

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

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

а)  если N чётное, то к дво­ич­ной за­пи­си слева до­пи­сы­ва­ет­ся 10;

б)  если N нечётное, то к нему спра­ва при­пи­сы­ва­ют­ся два нуля, а слева еди­ни­ца.

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

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

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

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

По­вто­ри 2 [Вперёд 10 На­пра­во 90 Вперёд 18 На­пра­во 90]

Под­нять хвост

Вперёд 5 На­пра­во 90 Вперёд 7 На­ле­во 90

Опу­стить хвост

По­вто­ри 2 [Вперёд 10 На­пра­во 90 Вперёд 7 На­пра­во 90].

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

При­бор ав­то­ма­ти­че­ской фик­са­ции на­ру­ше­ний пра­вил до­рож­но­го дви­же­ния де­ла­ет цвет­ные фо­то­гра­фии раз­ме­ром 1024 × 960 пик­се­лей, ис­поль­зуя па­лит­ру из 8192 цве­тов. Сним­ки со­хра­ня­ют­ся в па­мя­ти ка­ме­ры, груп­пи­ру­ют­ся в па­ке­ты по не­сколь­ко штук, а затем пе­ре­да­ют­ся в центр об­ра­бот­ки ин­фор­ма­ции со ско­ро­стью пе­ре­да­чи дан­ных 1 474 560 бит/⁠с. Ка­ко­во мак­си­маль­но воз­мож­ное число сним­ков в одном па­ке­те, если на пе­ре­да­чу од­но­го па­ке­та от­во­дит­ся не более 280 се­кунд.

Опре­де­ли­те ко­ли­че­ство 12-⁠рич­ных ше­сти­знач­ных чисел, в за­пи­си ко­то­рых ровно одна цифра 7 и не более трёх цифр с чис­ло­вым зна­че­ни­ем, пре­вы­ша­ю­щих 9.

Все пя­ти­бук­вен­ные слова, со­став­лен­ные из букв К, О, М, П, Ь, Т, Е, Р, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке и про­ну­ме­ро­ва­ны.

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

1.  ЕЕЕЕЕ

2.  ЕЕЕЕК

3.  ЕЕЕЕМ

4.  ЕЕЕЕО

5.  ЕЕЕЕП

6.  ЕЕЕЕР

7.  ЕЕЕЕТ

8.  ЕЕЕЕЬ

...

Под каким но­ме­ром в спис­ке стоит по­след­нее слово, ко­то­рое не со­дер­жит букв К и со­дер­жит ровно две буквы Р?

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

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

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

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

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

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

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

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

На пред­при­я­тии каж­дой из­го­тов­лен­ной де­та­ли при­сва­и­ва­ют се­рий­ный номер дли­ною 261 сим­вол. Для его хра­не­ния от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное число байт. При этом ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние се­рий­ных но­ме­ров, все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным чис­лом бит. Из­вест­но, что для хра­не­ния 862 се­рий­ных но­ме­ров от­ве­де­но не более 276 Кбайт па­мя­ти. Опре­де­ли­те мак­си­маль­но воз­мож­ную мощ­ность ал­фа­ви­та, из ко­то­ро­го со­став­ля­ют­ся се­рий­ные но­ме­ра.

Ме­тео­ро­ло­ги­че­ская стан­ция ведет на­блю­де­ние за влаж­но­стью воз­ду­ха. Ре­зуль­та­том од­но­го на­блю­де­ния яв­ля­ет­ся целое число от 0 до 100%, за­пи­сы­ва­е­мое при по­мо­щи ми­ни­маль­но воз­мож­но­го ко­ли­че­ства бит. Стан­ция сде­ла­ла 80 из­ме­ре­ний. Опре­де­ли­те ин­фор­ма­ци­он­ный объем ре­зуль­та­тов на­блю­де­ний. (Ответ дайте в бай­тах.)

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му объ­ек­ту при­сва­и­ва­ет­ся иден­ти­фи­ка­тор, со­сто­я­щий из 317 сим­во­лов и со­дер­жа­щий толь­ко де­ся­тич­ные цифры и сим­во­лы из 4090-⁠сим­воль­но­го спе­ци­аль­но­го ал­фа­ви­та. В базе дан­ных для хра­не­ния каж­до­го иден­ти­фи­ка­то­ра от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние иден­ти­фи­ка­то­ров, все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Опре­де­ли­те объём па­мя­ти (в Мбайт), не­об­хо­ди­мый для хра­не­ния 262 144 иден­ти­фи­ка­то­ров. В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство Мбайт.

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

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

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

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

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

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

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

Цикл

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

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

    КОНЕЦ ПОКА

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

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

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

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

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

    КОНЕЦ ЕСЛИ

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

Какая стро­ка по­лу­чит­ся в ре­зуль­та­те при­ме­не­ния при­ведённой ниже про­грам­мы к стро­ке, со­сто­я­щей из 84 иду­щих под­ряд цифр 8? В от­ве­те за­пи­ши­те по­лу­чен­ную стро­ку.

НА­ЧА­ЛО

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

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

            ТО за­ме­нить (1111, 8)

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

        КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

КОНЕЦ

Два узла, на­хо­дя­щи­е­ся в одной сети, имеют IP-⁠ад­ре­са 115.127.30.120 и 115.127.151.120. Ука­жи­те наи­боль­шее воз­мож­ное зна­че­ние тре­тье­го слева байта маски сети. Ответ за­пи­ши­те в виде де­ся­тич­но­го числа.

В тер­ми­но­ло­гии сетей ТСР/⁠IP мас­кой сети на­зы­ва­ет­ся дво­ич­ное число, опре­де­ля­ю­щее, какая часть IP-⁠ад­ре­са узла сети от­но­сит­ся к ад­ре­су сети, а какая  — к ад­ре­су са­мо­го узла в этой сети. При этом в маске сна­ча­ла (в стар­ших раз­ря­дах) стоят еди­ни­цы, а затем с не­ко­то­ро­го места  — нули. Обыч­но маска за­пи­сы­ва­ет­ся по тем же пра­ви­лам, что и IP-⁠адрес,  — в виде четырёх бай­тов, причём каж­дый байт за­пи­сы­ва­ет­ся в виде де­ся­тич­но­го числа. Адрес сети по­лу­ча­ет­ся в ре­зуль­та­те при­ме­не­ния по­раз­ряд­ной конъ­юнк­ции к за­дан­но­му IP-⁠ад­ре­су узла и маске. На­при­мер, если IP-⁠адрес узла равен 131.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 131.32.240.0.

Для узла с IP-⁠ад­ре­сом 170.155.137.181 адрес сети равен 170.155.136.0. Чему равно наи­боль­шее воз­мож­ное зна­че­ние тре­тье­го слева байта маски? Ответ за­пи­ши­те в виде де­ся­тич­но­го числа.

В тер­ми­но­ло­гии сетей ТСР/⁠IP мас­кой сети на­зы­ва­ют дво­ич­ное число, ко­то­рое по­ка­зы­ва­ет, какая часть IP-⁠ад­ре­са узла сети от­но­сит­ся к ад­ре­су сети, а какая  — к ад­ре­су узла в этой сети. Адрес сети по­лу­ча­ет­ся в ре­зуль­та­те при­ме­не­ния по­раз­ряд­ной конъ­юнк­ции к за­дан­но­му ад­ре­су узла и его маске. Сеть за­да­на IP-⁠ад­ре­сом 112.160.0.0 и се­те­вой мас­кой 255.240.0.0.

Сколь­ко в этой сети IP-⁠ад­ре­сов, для ко­то­рых ко­ли­че­ство еди­ниц в дво­ич­ной за­пи­си IP-⁠ад­ре­са не крат­но 5?

В от­ве­те ука­жи­те толь­ко число.

Зна­че­ние ариф­ме­ти­че­ско­го вы­ра­же­ния 3¹⁰⁰  — х, где х  — целое по­ло­жи­тель­ное число, не пре­вы­ша­ю­щее 2030, за­пи­са­ли в тро­ич­ной си­сте­ме счис­ле­ния. Опре­де­ли­те наи­мень­шее зна­че­ние х, при ко­то­ром в тро­ич­ной за­пи­си числа, яв­ля­ю­ще­го­ся зна­че­ни­ем дан­но­го ариф­ме­ти­че­ско­го вы­ра­же­ния, со­дер­жит­ся ровно два нуля.

В от­ве­те за­пи­ши­те число в де­ся­тич­ной си­сте­ме счис­ле­ния.

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

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

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

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

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

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

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

Чему равно зна­че­ние вы­ра­же­ния (F(2024) − 4 · F(2023)) / F(2022)?

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

Ответ:

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

Если най­де­но не­сколь­ко зна­че­ний S, в от­ве­те за­пи­ши­те ми­ни­маль­ное из них.

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

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

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

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

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

Найти под­по­сле­до­ва­тель­ность мак­си­маль­ной длины, ко­то­рая имеет ариф­ме­ти­че­ский смысл и со­дер­жит толь­ко цифры 6, 7, 8, 0 и знаки опе­ра­ций «−», «*». При этом долж­ны вы­пол­нять­ся сле­ду­ю­щие усло­вия:

Возле цифры 0 не может быть знака опе­ра­ции.

В вы­ра­же­нии не долж­но быть умно­же­ния на от­ри­ца­тель­ные числа.

В вы­ра­же­нии не долж­но быть по­вто­ря­ю­щих­ся зна­ков опе­ра­ций, таких как «**».

При­мер пра­виль­но­го вы­ра­же­ния: 6787-86.

При­мер не­пра­виль­но­го вы­ра­же­ния: 6786*−78 (со­дер­жит по­вто­ря­ю­щи­е­ся знаки опе­ра­ции и от­ри­ца­тель­ное число).

В от­ве­те за­пи­ши­те длину най­ден­ной по­сле­до­ва­тель­но­сти.

При он­лайн-⁠по­куп­ке би­ле­та на кон­церт из­вест­но, какие места в зале уже за­ня­ты. Не­об­хо­ди­мо ку­пить два би­ле­та на такие со­сед­ние места в одном ряду, чтобы перед ними все крес­ла с та­ки­ми же но­ме­ра­ми были сво­бод­ны, а ряд на­хо­дил­ся как можно даль­ше от сцены. Если в этом ряду таких пар мест не­сколь­ко, най­ди­те пару с наи­боль­ши­ми но­ме­ра­ми. В от­ве­те за­пи­ши­те два целых числа: ис­ко­мый номер ряда и наи­боль­ший номер места в най­ден­ной паре. Ну­ме­ра­ция рядов и мест ведётся с 1. Га­ран­ти­ру­ет­ся, что хотя бы одна такая пара в зале есть.

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

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

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

Два целых по­ло­жи­тель­ных числа: наи­боль­ший номер ряда и наи­боль­ший номер места в най­ден­ной паре кре­сел.

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

7 7 8

1 1

6 6

5 5

6 7

4 4

2 2

3 3

При таких ис­ход­ных дан­ных от­ве­том яв­ля­ет­ся пара чисел 5 и 8. Усло­вию за­да­чи удо­вле­тво­ря­ют места 7 и 8 в ряду 5: перед крес­ла­ми 7 и 8 нет за­ня­тых мест и это по­след­няя из двух воз­мож­ных пар в этом ряду. В рядах 6 и 7 ис­ко­мую пару найти нель­зя.

Ответ:

Отбор аби­ту­ри­ен­тов в вуз про­ис­хо­дит по сумме бал­лов трех эк­за­ме­нов: по рус­ско­му языку, ма­те­ма­ти­ке и ин­фор­ма­ти­ке. На за­ра­нее из­вест­ное ко­ли­че­ство мест за­чис­ля­ют­ся аби­ту­ри­ен­ты, на­брав­шие боль­шую сумму бал­лов по ре­зуль­та­там трех эк­за­ме­нов. Все аби­ту­ри­ен­ты, на­брав­шие опре­де­лен­ную сумму бал­лов или боль­ше, за­чис­ля­ют­ся на име­ю­щи­е­ся места. Такой балл на­зы­ва­ет­ся про­ход­ным. Если после за­пол­не­ния име­ю­щих­ся мест аби­ту­ри­ен­та­ми с про­ход­ным бал­лом оста­ют­ся не­за­пол­нен­ные места, но аби­ту­ри­ен­тов, на­брав­ших сле­ду­ю­щую сумму бал­лов, боль­ше, чем ва­кант­ных мест, на­бран­ная этими аби­ту­ри­ен­та­ми сумма бал­лов на­зы­ва­ет­ся по­лу­про­ход­ным бал­лом. Из числа аби­ту­ри­ен­тов, на­брав­ших по­лу­про­ход­ной балл, на име­ю­щи­е­ся места при­ни­ма­ют­ся аби­ту­ри­ен­ты, име­ю­щие более вы­со­кий балл по ма­те­ма­ти­ке, а при ра­вен­стве бал­лов по ма­те­ма­ти­ке  — по ин­фор­ма­ти­ке.

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

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

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

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

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

4 2

60 75 90

65 70 90

50 80 100

40 95 80

При таких ис­ход­ных дан­ных про­ход­ной балл равен 230, по­лу­про­ход­ной 225, на остав­ше­е­ся одно место будет за­чис­лен аби­ту­ри­ент, на­брав­ший в сумме 225 бал­лов и по­лу­чив­ший по ин­фор­ма­ти­ке 90 бал­лов.

Ответ:

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

Ответ: