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

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

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

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

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

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

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

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

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

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

Все за­глав­ные буквы рус­ско­го ал­фа­ви­та за­ко­ди­ро­ва­ны не­рав­но­мер­ным дво­ич­ным кодом, в ко­то­ром ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это усло­вие обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний. Из­вест­ны ко­до­вые слова пер­вых букв ал­фа­ви­та: А  — 001, Б  — 011, В  — 110. Какую наи­мень­шую длину может иметь код слова ВО­ДО­ПРО­ВОД?

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

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

2.  Под­счи­ты­ва­ет­ся ко­ли­че­ство нулей и еди­ниц в по­лу­чен­ной за­пи­си. Если их ко­ли­че­ство оди­на­ко­во, в конец за­пи­си до­бав­ля­ет­ся её по­след­няя цифра. В про­тив­ном слу­чае в конец за­пи­си до­бав­ля­ет­ся та цифра, ко­то­рая встре­ча­ет­ся реже.

3.  Шаг 2 по­вто­ря­ет­ся ещё два раза

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

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

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

2.  В по­лу­чен­ной за­пи­си нулей мень­ше, чем еди­ниц, в конец за­пи­си до­бав­ля­ет­ся 0. Новая за­пись: 100110.

3.  В те­ку­щей за­пи­си нулей и еди­ниц по­ров­ну, в конец за­пи­сы­ва­ет­ся по­след­няя цифра, это 0. По­лу­ча­ет­ся 1001100. В этой за­пи­си еди­ниц мень­ше, в конец до­бав­ля­ет­ся 1: 10011001.

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

При каком наи­мень­шем числе N > 99 в ре­зуль­та­те ра­бо­ты ал­го­рит­ма по­лу­чит­ся число, крат­ное 4?

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

В на­чаль­ный мо­мент Че­ре­па­ха на­хо­дит­ся в на­ча­ле ко­ор­ди­нат и на­прав­ле­на вверх (вдоль по­ло­жи­тель­но­го на­прав­ле­ния оси ор­ди­нат).

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

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

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

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

За­пись о до­ку­мен­те в ин­фор­ма­ци­он­ной си­сте­ме со­дер­жит его текст и от­ска­ни­ро­ван­ную копию, по­лу­чен­ную ска­ни­ро­ва­ни­ем с раз­ре­ше­ни­ем 150 dpi и сжа­ти­ем по­лу­чен­но­го изоб­ра­же­ния на 20%. При этом текст до­ку­мен­та за­ни­ма­ет 50% всего объёма за­пи­си. Сколь­ко про­цен­тов объёма за­пи­си будет за­ни­мать текст до­ку­мен­та, если за­ме­нить от­ска­ни­ро­ван­ную копию на новую, сде­лан­ную с раз­ре­ше­ни­ем 300 dpi и сжа­ти­ем изоб­ра­же­ния на 40%?

В от­ве­те за­пи­ши­те толь­ко число (ко­ли­че­ство про­цен­тов), без знака %.

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

1.  ААААА

2.  ААААК

3.  ААААР

4.  ААААУ

5.  АААКА

...

Ука­жи­те номер пер­во­го слова, ко­то­рое на­чи­на­ет­ся с буквы К.

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

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

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

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

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

Каж­дый со­труд­ник пред­при­я­тия по­лу­ча­ет элек­трон­ный про­пуск, на ко­то­ром за­пи­са­ны лич­ный код со­труд­ни­ка и срок дей­ствия про­пус­ка. Лич­ный код со­сто­ит из 22 сим­во­лов, каж­дый из ко­то­рых может быть одной из 26 за­глав­ных ла­тин­ских букв. Для за­пи­си кода на про­пус­ке от­ве­де­но ми­ни­маль­но воз­мож­ное целое число бай­тов, при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым ми­ни­маль­но воз­мож­ным ко­ли­че­ством битов. Срок дей­ствия за­пи­сы­ва­ет­ся как номер года (число от 0 до 99, озна­ча­ю­щее год от 2000 до 2099) и номер дня в году (число от 1 до 366).

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

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

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

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

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

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

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

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

Цикл

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

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

    КОНЕЦ ПОКА

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

НА­ЧА­ЛО

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

        за­ме­нить (01, 210)

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

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

    КОНЕЦ ПОКА

КОНЕЦ

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

На месте пре­ступ­ле­ния были об­на­ру­же­ны че­ты­ре об­рыв­ка бу­ма­ги. След­ствие уста­но­ви­ло, что на них за­пи­са­ны фраг­мен­ты од­но­го IP-⁠ад­ре­са. Кри­ми­на­ли­сты обо­зна­чи­ли эти фраг­мен­ты бук­ва­ми А, Б, В и Г. Вос­ста­но­ви­те IP-⁠адрес. В от­ве­те ука­жи­те по­сле­до­ва­тель­ность букв, обо­зна­ча­ю­щих фраг­мен­ты, в по­ряд­ке, со­от­вет­ству­ю­щем IP-⁠ад­ре­су. Если будет не­сколь­ко ва­ри­ан­тов ре­ше­ния, за­пи­ши­те их все через за­пя­тую.

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

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

На чис­ло­вой пря­мой даны два от­рез­ка: P  =  [10, 29] и Q  =  [13, 18].

Ука­жи­те наи­боль­шую воз­мож­ную длину от­рез­ка A, для ко­то­ро­го вы­ра­же­ние

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

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

F(n)  =  2 при n < 3;

F(n)  =  F(n − 2) + F(n − 1) − n, если n > 2 и при этом n чётно;

F(n) =F(n − 1) − F(n − 2) + 2 × n, если n > 2 и при этом n нечётно.

Чему равно зна­че­ние функ­ции F(32)?

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

Ответ:

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

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

При­мер вход­ных дан­ных (для таб­ли­цы раз­ме­ром 4 × 4):

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может

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

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

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

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может

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

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

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

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

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

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

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может

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

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

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

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

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

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

Ис­пол­ни­тель ТР4 пре­об­ра­зу­ет число на экра­не.

У ис­пол­ни­те­ля есть две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра.

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

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

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

Про­грам­ма для ис­пол­ни­те­ля ТР4  — это по­сле­до­ва­тель­ность ко­манд.

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

Тра­ек­то­рия вы­чис­ле­ний  — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 212 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 14, 15, 30.

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

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

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N  — общее ко­ли­че­ство чисел в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число.

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

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

6

3

8

14

11

22

17 В дан­ном слу­чае есть две под­хо­дя­щие пары: 3 и 8 (сумма 11), 3 и 14 (сумма 17). В от­ве­те надо за­пи­сать числа 2 и 17.

Ответ:

Гео­де­зист из­ме­ря­ет вы­со­ту над уров­нем моря (в мил­ли­мет­рах) от­но­си­тель­но уров­ня на­ча­ла до­ро­ги, для каж­дой из N её мет­ро­вых от­ме­ток. Ну­ме­ра­ция от­ме­ток на­чи­на­ет­ся с еди­ни­цы.

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

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

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

Даны два вход­ных файла (файл А и файл В), каж­дый из ко­то­рых в пер­вой стро­ке вход­ных дан­ных задаётся про­тя­жен­ность до­ро­ги N (1 ≤ N ≤ 10 000), а во вто­рой  — на­ту­раль­ное число К  — ми­ни­маль­но до­пу­сти­мое рас­сто­я­ние (в мет­рах) между двумя от­мет­ка­ми до­ро­ги (N > К).

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

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла А, затем  — для файла В.

Ответ: