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

Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, то ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Опре­де­ли­те, ка­ко­ва длина до­ро­ги из пунк­та Б в пункт В. В от­ве­те за­пи­ши­те целое число  — так, как оно ука­за­но в таб­ли­це.

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

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

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

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

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

Таб­ли­ца «На­чис­ле­ния» со­дер­жит за­пи­си о на­чис­ле­ни­ях. За­го­ло­вок таб­ли­цы имеет вид:

Таб­ли­ца «Ли­це­вые счета» со­дер­жит ин­фор­ма­цию о ма­га­зи­нах, в ко­то­рых ре­а­ли­зу­ют­ся то­ва­ры фирмы. За­го­ло­вок таб­ли­цы имеет вид:

Таб­ли­ца «Отдел» со­дер­жит ин­фор­ма­цию об от­де­лах ком­па­нии.

За­го­ло­вок таб­ли­цы имеет вид:

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

Ис­поль­зуя ин­фор­ма­цию из при­ведённой базы дан­ных, опре­де­ли­те сум­мар­ные до­хо­ды (в руб­лях) Про­из­вод­ствен­но­го цеха в от­де­ле ма­га­зи­на «Сан­тех­ни­ка» на улице Се­мео­нов­ская, дом 27 за 2021 год.

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

Все за­глав­ные буквы рус­ско­го ал­фа­ви­та за­ко­ди­ро­ва­ны не­рав­но­мер­ным дво­ич­ным кодом, в ко­то­ром ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это усло­вие обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний. Из­вест­ны ко­до­вые слова не­ко­то­рых букв: Л  — 000, Р  — 11, С  — 100. Какое наи­мень­шее число дво­ич­ных зна­ков может со­дер­жать код слова КО­РО­БОК?

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

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

2.  Если N не крат­но 3, то оста­ток от де­ле­ния на 3 умно­жа­ет­ся на 5, пе­ре­во­дит­ся в тро­ич­ную за­пись и до­пи­сы­ва­ет­ся в конец числа.

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

Ука­жи­те ми­ни­маль­ное число N, после об­ра­бот­ки ко­то­ро­го ав­то­мат по­лу­ча­ет число, боль­шее 146.

Ис­пол­ни­тель Цапля дей­ству­ет на плос­ко­сти с де­кар­то­вой си­сте­мой ко­ор­ди­нат. В на­чаль­ный мо­мент Цапля на­хо­дит­ся в на­ча­ле ко­ор­ди­нат, её клюв на­прав­лен вдоль по­ло­жи­тель­но­го на­прав­ле­ния оси ор­ди­нат, клюв опу­щен. При опу­щен­ном клюве Цапля остав­ля­ет на поле след в виде линии. В каж­дый кон­крет­ный мо­мент из­вест­но по­ло­же­ние ис­пол­ни­те­ля и на­прав­ле­ние его дви­же­ния. У ис­пол­ни­те­ля су­ще­ству­ет три ко­ман­ды: Вперёд n (где n  — целое число), вы­зы­ва­ю­щая пе­ре­дви­же­ние Цапли на n еди­ниц в том на­прав­ле­нии, куда ука­зы­ва­ет её клюв; На­пра­во m (где m  — целое число), вы­зы­ва­ю­щая из­ме­не­ние на­прав­ле­ния дви­же­ния на m гра­ду­сов по ча­со­вой стрел­ке; Дуга r, a, b, α (где r, a, b, α  — целые числа), вы­зы­ва­ю­щая пе­ре­дви­же­ние Цапли из те­ку­щей точки с ко­ор­ди­на­та­ми (x, y) по дуге окруж­но­сти с цен­тром в точке с ко­ор­ди­на­та­ми и ра­ди­у­сом r, гра­дус­ная мера дуги равна α, дви­же­ние по дуге идёт по ча­со­вой стрел­ке.

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

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

На­пра­во 180 Вперёд 2 На­пра­во 90 Вперёд 40 На­пра­во 90 Вперёд 2 По­вто­ри 4 [Дуга 5, 5, 0, 180].

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

Для хра­не­ния про­из­воль­но­го раст­ро­во­го изоб­ра­же­ния раз­ме­ром 1536 × 2048 пик­се­лей от­ве­де­но не более 6 Мбайт па­мя­ти без учёта раз­ме­ра за­го­лов­ка файла. Для ко­ди­ро­ва­ния цвета каж­до­го пик­се­ля ис­поль­зу­ет­ся оди­на­ко­вое ко­ли­че­ство бит, коды пик­се­лей за­пи­сы­ва­ют­ся в файл один за дру­гим без про­ме­жут­ков. Какое мак­си­маль­ное ко­ли­че­ство цве­тов можно ис­поль­зо­вать в изоб­ра­же­нии?

Все 4-⁠бук­вен­ные слова, со­став­лен­ные из букв Д, Е, К, О, Р, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке и про­ну­ме­ро­ва­ны, на­чи­ная с 1. Ниже при­ве­де­но на­ча­ло спис­ка.

1.   ДДДД

2.   ДДДЕ

3.   ДДДК

4.   ДДДО

5.   ДДДР

6.   ДДЕД

...

Под каким но­ме­ром в спис­ке идёт пер­вое слово, ко­то­рое на­чи­на­ет­ся с буквы K?

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

Текст по­ве­сти Алек­сандра Куп­ри­на «По­еди­нок» пред­став­лен в виде фай­лов раз­лич­ных фор­ма­тов. От­крой­те один из фай­лов и опре­де­ли­те, сколь­ко раз в тек­сте встре­ча­ют­ся ком­би­на­ция сим­во­лов «Час» или «час», не яв­ля­ю­щи­е­ся от­дель­ны­ми сло­ва­ми.

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

На пред­при­я­тии каж­дой из­го­тов­лен­ной де­та­ли при­сва­и­ва­ют се­рий­ный номер, со­дер­жа­щий де­ся­тич­ные цифры, 52 ла­тин­ские буквы (с учётом ре­ги­стра) и сим­во­лы из 963⁠-⁠сим­воль­но­го спе­ци­аль­но­го ал­фа­ви­та. В базе дан­ных для хра­не­ния каж­до­го се­рий­но­го но­ме­ра от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное число байт. При этом ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние се­рий­ных но­ме­ров, все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным чис­лом бит. Из­вест­но, что для хра­не­ния 2000 се­рий­ных но­ме­ров от­ве­де­но не более 693 Кбайт па­мя­ти. Опре­де­ли­те мак­си­маль­но воз­мож­ную длину се­рий­но­го но­ме­ра. В от­ве­те за­пи­ши­те толь­ко целое число.

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

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

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

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

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

 Цикл

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

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

    КОНЕЦ ПОКА

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

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

НА­ЧА­ЛО

ПОКА на­шлось (19) ИЛИ на­шлось (399) ИЛИ на­шлось (999)

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

        ТО за­ме­нить (19, 9)

    КОНЕЦ ЕСЛИ

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

        ТО за­ме­нить (399, 91)

    КОНЕЦ ЕСЛИ

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

        ТО за­ме­нить (999, 3)

    КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

На вход при­ведённой выше про­грам­ме по­сту­па­ет стро­ка, на­чи­на­ю­ща­я­ся с цифры «1», а затем со­дер­жа­щая n цифр «9» (3 < n < 10 000).

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

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

Зна­че­ние вы­ра­же­ния за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 7 без не­зна­ча­щих нулей. Какая цифра чаще всего встре­ча­ет­ся в этой за­пи­си?

На чис­ло­вой пря­мой даны три от­рез­ка: P  =  [10, 40], Q  =  [5, 15] и R  =  [35, 50]. Ка­ко­ва наи­мень­шая воз­мож­ная длина про­ме­жут­ка A, что фор­му­ла

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

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

F(0)  =  0;

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

F(n)  =  1 + F(n − 1), если n нечётно.

Сколь­ко су­ще­ству­ет таких чисел n, что 1 ≤ n ≤ 500 и F(n)  =  3?

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

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

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

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

—  сумма эле­мен­тов трой­ки боль­ше мак­си­маль­но­го эле­мен­та по­сле­до­ва­тель­но­сти, за­пись ко­то­ро­го за­кан­чи­ва­ет­ся на 123. (Га­ран­ти­ру­ет­ся, что в по­сле­до­ва­тель­но­сти есть хотя бы один эле­мент, за­пись ко­то­ро­го за­кан­чи­ва­ет­ся на 123.)

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

Ответ:

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

Шаг впра­во раз­ре­ша­ет­ся сде­лать толь­ко в клет­ку с чис­лом той же чётно­сти, шаг вниз  — толь­ко в клет­ку с чис­лом дру­гой чётно­сти. Шаг по диа­го­на­ли воз­мо­жен все­гда.

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

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

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це. При­мер вход­ных дан­ных (для таб­ли­цы раз­ме­ром 4 × 4):

При ука­зан­ных вход­ных дан­ных мак­си­маль­ное зна­че­ние 250 по­лу­чит­ся при дви­же­нии по марш­ру­ту 53 → 63 → 62 → 59 → 13. Не­до­ступ­ны для ро­бо­та клет­ки с чис­ла­ми 18, 80, 2, 86  — всего 4 клет­ки. В от­ве­те в дан­ном слу­чае надо за­пи­сать числа 250 и 4.

Ответ:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.  Умно­жить на 3.

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

Про­грам­ма для ис­пол­ни­те­ля  — это по­сле­до­ва­тель­ность ко­манд. На­при­мер, если в на­чаль­ный мо­мент на экра­не на­хо­дит­ся число 1, то про­грам­ма 213 по­сле­до­ва­тель­но пре­об­ра­зу­ет его в 3, 4, 8.

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

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

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

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

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

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

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

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

На­пи­ши­те про­грам­му, ко­то­рая ищет среди целых чисел, при­над­ле­жа­щих чис­ло­во­му от­рез­ку [125 256; 125 330], числа, име­ю­щие ровно шесть раз­лич­ных чётных на­ту­раль­ных де­ли­те­лей. Для каж­до­го най­ден­но­го числа за­пи­ши­те эти шесть де­ли­те­лей в шесть со­сед­них столб­цов на экра­не с новой стро­ки. Де­ли­те­ли в стро­ке долж­ны сле­до­вать в по­ряд­ке воз­рас­та­ния.

На­при­мер, в диа­па­зо­не [2; 48] ровно шесть чётных раз­лич­ных на­ту­раль­ных де­ли­те­лей имеют числа 24, 36 и 40, по­это­му для этого диа­па­зо­на вывод на экра­не долж­на со­дер­жать сле­ду­ю­щие зна­че­ния:

2 4 6 8 12 24

2 4 6 12 18 36

2 4 8 10 20 40

Ответ:

Дано N де­та­лей, номер де­та­ли сов­па­да­ет со стро­кой, и счи­та­ет­ся от 1 до N, в N стро­ках со­от­вет­ствен­но: время шли­фов­ки, время по­крас­ки. Есть кон­вей­ер­ная лента длины N, тре­бу­ет­ся от­шли­фо­вать и по­кра­сить де­та­ли, их ста­вят на кон­вей­ер­ную ленту сле­ду­ю­щим об­ра­зом: стро­ит­ся по­сле­до­ва­тель­ность 2 · N, все числа дан­ные в парах сор­ти­ру­ют­ся по воз­рас­та­нию в этой по­сле­до­ва­тель­но­сти от наи­мень­ше­го к наи­боль­ше­му.

Если ми­ни­маль­ное время  — время шли­фов­ки, то де­таль ста­вит­ся в первую сво­бод­ную ячей­ку с на­ча­ла.

Если ми­ни­маль­ное время  — время по­крас­ки, де­таль ста­вит­ся в первую сво­бод­ную ячей­ку с конца.

Если ми­ни­маль­ное число время окра­ши­ва­ния или шли­фов­ки уже рас­смот­рен­ной де­та­ли, такое время иг­но­ри­ру­ет­ся.

По­лу­ча­ет­ся за­пол­нен­ная лента об­ра­бот­ки.

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

Пер­вая стро­ка вход­но­го файла со­дер­жит на­ту­раль­ное число N (1 ≤ N ≤ 1000)  — ко­ли­че­ство де­та­лей. Сле­ду­ю­щие N строк со­дер­жат пары чисел, обо­зна­ча­ю­щих со­от­вет­ствен­но время шли­фов­ки и время окра­ши­ва­ния кон­крет­ной де­та­ли (все числа на­ту­раль­ные, раз­лич­ные).

Опре­де­ли­те номер по­след­ней де­та­ли, по­став­лен­ной на кон­вей­ер и ко­ли­че­ство де­та­лей от­шли­фо­ван­ных до неё.

За­да­ние вы­пол­ня­ет­ся с ис­поль­зо­ва­ни­ем при­ла­га­е­мых фай­лов.

По ка­на­лу связи пе­ре­даётся по­сле­до­ва­тель­ность целых чисел  — по­ка­за­ния при­бо­ра, по­лу­чен­ные с ин­тер­ва­лом 1 мин. в те­че­ние N мин. (N  — на­ту­раль­ное число). При­бор из­ме­ря­ет зна­че­ние за­ря­да ча­стиц, по­лу­чен­ное ре­ги­стра­то­ром за ми­ну­ту, пред­ше­ству­ю­щую мо­мен­ту ре­ги­стра­ции, и пе­ре­даёт это зна­че­ние в услов­ных еди­ни­цах из­ме­ре­ния.

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

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

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

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

За­пи­ши­те в от­ве­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла A, затем  — для файла B.

Ответ: