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

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

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

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

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

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

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко буквы из на­бо­ра: А, З, К, Н, Ч. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий пря­мо­му усло­вию Фано, со­глас­но ко­то­ро­му ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это усло­вие обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: Н  — 1111, З  — 110. Для трёх остав­ших­ся букв А, К и Ч ко­до­вые слова не­из­вест­ны.

Какое ко­ли­че­ство дво­ич­ных зна­ков по­тре­бу­ет­ся для ко­ди­ро­ва­ния слова КА­ЗАЧ­КА, если из­вест­но, что оно за­ко­ди­ро­ва­но ми­ни­маль­но воз­мож­ным ко­ли­че­ством дво­ич­ных зна­ков?

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

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

2.  К этой за­пи­си до­пи­сы­ва­ет­ся спра­ва два нуля, если число чет­ное, или две еди­ни­цы в про­тив­ном слу­чае

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

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

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

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

По­вто­ри 5 [Дуга 5, 0, 5, 180 Дуга 5, 5, 0, 180 Дуга 5, 0, -5, 180 Дуга 5, -5, 0, 180].

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

Для про­ве­де­ния экс­пе­ри­мен­та со­зда­ют­ся изоб­ра­же­ния, со­дер­жа­щие слу­чай­ные на­бо­ры цвет­ных пик­се­лей. Раз­мер изоб­ра­же­ния  — 640 x 480 пк, при со­хра­не­нии изоб­ра­же­ния каж­дый пик­сель ко­ди­ру­ет­ся оди­на­ко­вым чис­лом битов, все коды пик­се­лей за­пи­сы­ва­ют­ся под­ряд, ме­то­ды сжа­тия не ис­поль­зу­ют­ся. Раз­мер файла не дол­жен пре­вы­шать 280 Кбайт, при этом 40 Кбайт не­об­хо­ди­мо вы­де­лить для слу­жеб­ной ин­фор­ма­ции. Какое мак­си­маль­ное ко­ли­че­ство раз­лич­ных цве­тов и от­тен­ков можно ис­поль­зо­вать в изоб­ра­же­нии?

Игорь со­став­ля­ет таб­ли­цу ко­до­вых слов для пе­ре­да­чи со­об­ще­ний, каж­до­му со­об­ще­нию со­от­вет­ству­ет своё ко­до­вое слово. В ка­че­стве ко­до­вых слов Игорь ис­поль­зу­ет 5-⁠бук­вен­ные слова, в ко­то­рых есть толь­ко буквы A, B, C, X, причём буква X по­яв­ля­ет­ся ровно 1 раз и толь­ко на 1-⁠й или по­след­ней по­зи­ции слова. Каж­дая из дру­гих до­пу­сти­мых букв может встре­чать­ся в ко­до­вом слове любое ко­ли­че­ство раз или не встре­чать­ся со­всем. Сколь­ко раз­лич­ных ко­до­вых слов может ис­поль­зо­вать Игорь?

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

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

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

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

Опре­де­ли­те, сколь­ко раз в тек­сте про­из­ве­де­ния А. С. Пуш­ки­на «Ка­пи­тан­ская дочка» встре­ча­ет­ся слово «дочка» или «Дочка». Дру­гие формы этого слова («дочку», «дочки» и т. д.) учи­ты­вать не надо.

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 23 сим­во­лов. В ка­че­стве сим­во­лов ис­поль­зу­ют­ся буквы из 12-⁠сим­воль­но­го ал­фа­ви­та. В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Кроме соб­ствен­но па­ро­ля в си­сте­ме хра­нят­ся до­пол­ни­тель­ные све­де­ния о каж­дом поль­зо­ва­те­ле, для чего вы­де­ле­но целое число байт; это число одно и то же для всех поль­зо­ва­те­лей.

Для хра­не­ния све­де­ний о 297 поль­зо­ва­те­лях по­тре­бо­ва­лось 13 068 байт. Сколь­ко байт вы­де­ле­но для хра­не­ния до­пол­ни­тель­ных све­де­ний об одном поль­зо­ва­те­ле?

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

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

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

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

на­шлось (v)

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

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

НА­ЧА­ЛО

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

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

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

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

                КОНЕЦ ПОКА

КОНЕЦ

Из­вест­но, что ис­ход­ная стро­ка на­чи­на­лась с нуля и за­кан­чи­ва­лась нулём, а между ними были толь­ко цифры 1, 2 и 3. После вы­пол­не­ния дан­ной про­грам­мы по­лу­чи­лась стро­ка, со­дер­жа­щая 96 еди­ниц, 0 двоек и 75 троек. Вы­ве­ди­те ми­ни­маль­ную длину ис­ход­ной стро­ки.

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

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

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

Обо­зна­чим через m&n по­раз­ряд­ную конъ­юнк­цию не­от­ри­ца­тель­ных целых чисел m и n.

Так, на­при­мер, 14&5  =  1110₂&0101₂  =  0100₂  =  4.

Для ка­ко­го наи­мень­ше­го не­от­ри­ца­тель­но­го це­ло­го числа А фор­му­ла

тож­де­ствен­но ис­тин­на (т. е. при­ни­ма­ет зна­че­ние 1 при любом не­от­ри­ца­тель­ном целом зна­че­нии пе­ре­мен­ной x)?

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

при

если и при этом n нечётно;

если и при этом n чётно.

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фор­мат вход­ных дан­ных.

В пер­вых двух стро­ках вход­но­го файла за­пи­са­ны зна­че­ния N (ко­ли­че­ство де­та­лей), K (ко­ли­че­ство кон­тей­не­ров). Сле­ду­ю­щие N строк со­дер­жат по од­но­му це­ло­му числу  — объём оче­ред­ной де­та­ли. Сле­ду­ю­щие K строк со­дер­жат по од­но­му це­ло­му числу  — объём каж­до­го кон­тей­не­ра.

Фор­мат вы­ход­ных дан­ных.

Про­грам­ма долж­ны вы­ве­сти два числа: пер­вое число равно объёму всех от­ло­жен­ных де­та­лей, вто­рое число  — их ко­ли­че­ство.

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

В пер­вой стро­ке вход­но­го файла на­хо­дит­ся число N  — ко­ли­че­ство де­та­лей (на­ту­раль­ное число, не пре­вы­ша­ю­щее 20 000). Во вто­рой стро­ке число K  — ко­ли­че­ство кон­вей­е­ров (на­ту­раль­ное число, не пре­вы­ша­ю­щее 20 000). Пер­вые N строк со­дер­жат одно целое число  — объём оче­ред­ной де­та­ли. Сле­ду­ю­щие K строк со­дер­жат объём каж­до­го кон­вей­е­ра.

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

Два целых не­от­ри­ца­тель­ных числа: пер­вое число равно объёму всех от­ло­жен­ных де­та­лей, вто­рое число  — их ко­ли­че­ство.

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

4

3

10

15

35

20

5

10

45

Для при­ведённого при­ме­ра от­ве­том яв­ля­ет­ся пара чисел: 45; 3.

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

Ответ:

Учёный решил про­ве­сти кла­сте­ри­за­цию не­ко­то­ро­го мно­же­ства звёзд по их рас­по­ло­же­нию на карте звёзд­но­го неба. Кла­стер звёзд  — это набор звёзд (точек) на гра­фи­ке, ле­жа­щий внут­ри пря­мо­уголь­ни­ка вы­со­той H и ши­ри­ной W. Каж­дая звез­да обя­за­тель­но при­над­ле­жит толь­ко од­но­му из кла­сте­ров.

Ис­тин­ный центр кла­сте­ра, или цен­т­ро­ид,  — это одна из звёзд на гра­фи­ке, сумма рас­сто­я­ний от ко­то­рой до всех осталь­ных звёзд кла­сте­ра ми­ни­маль­на. Под рас­сто­я­ни­ем по­ни­ма­ет­ся рас­сто­я­ние Ев­кли­да между двумя точ­ка­ми A(x₁, y₁) и B(x₂, y₂) на плос­ко­сти, ко­то­рое вы­чис­ля­ет­ся по фор­му­ле:

В файле A хра­нят­ся дан­ные о звёздах двух кла­сте­ров, где H  =  3, W  =  3 для каж­до­го кла­сте­ра. В каж­дой стро­ке за­пи­са­на ин­фор­ма­ция о рас­по­ло­же­нии на карте одной звез­ды: сна­ча­ла ко­ор­ди­на­та x, затем ко­ор­ди­на­та y. Зна­че­ния даны в услов­ных еди­ни­цах. Из­вест­но, что ко­ли­че­ство звёзд не пре­вы­ша­ет 1000.

В файле Б хра­нят­ся дан­ные о звёздах трёх кла­сте­ров, где H  =  3, W  =  3 для каж­до­го кла­сте­ра. Из­вест­но, что ко­ли­че­ство звёзд не пре­вы­ша­ет 10 000.

Струк­ту­ра хра­не­ния ин­фор­ма­ции о звез­дах в файле Б ана­ло­гич­на файлу А.

Для каж­до­го файла опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем вы­чис­ли­те два числа: P_x  — сред­нее ариф­ме­ти­че­ское абс­цисс цен­тров кла­сте­ров, и P_y  — сред­нее ариф­ме­ти­че­ское ор­ди­нат цен­тров кла­сте­ров.

В от­ве­те за­пи­ши­те че­ты­ре числа: в пер­вой стро­ке сна­ча­ла целую часть про­из­ве­де­ния P_x × 10 000 , затем целую часть про­из­ве­де­ния P_y × 10 000 для файла А, во вто­рой стро­ке  — ана­ло­гич­ные дан­ные для файла Б.

Воз­мож­ные дан­ные од­но­го из фай­лов ил­лю­стри­ро­ва­ны гра­фи­ком.

Ответ: