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

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

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

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

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

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

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

Таб­ли­ца «Про­дук­ция» со­дер­жит ин­фор­ма­цию о но­мен­кла­ту­ре вы­пус­ка­е­мой ме­бе­ли. За­го­ло­вок таб­ли­цы имеет вид:

Таб­ли­ца «Го­то­вый товар»  — ин­фор­ма­цию об уже ме­бе­ли. За­го­ло­вок таб­ли­цы имеет вид:

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

Ис­поль­зуя ин­фор­ма­цию из при­ведённой базы дан­ных, опре­де­ли­те общую сто­и­мость (в руб­лях) всех ди­ва­нов вы­кат­ных, про­из­ведённых на пред­при­я­ти­ях Моск­вы из де­ре­ва.

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

Все за­глав­ные буквы рус­ско­го ал­фа­ви­та за­ко­ди­ро­ва­ны не­рав­но­мер­ным дво­ич­ным кодом, в ко­то­ром ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это усло­вие обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: И  — 01, Н  — 110, Ф  — 00111, О  — 000, Р  — 111, М  — 10101, А  — 100, Т  — 0010, К  — 1011. Ука­жи­те воз­мож­ный код ми­ни­маль­ной длины для буквы Ю. Если таких кодов не­сколь­ко, ука­жи­те тот из них, ко­то­рый имеет ми­ни­маль­ное чис­ло­вое зна­че­ние.

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

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

2.  Скла­ды­ва­ют­ся все цифры по­лу­чен­ной дво­ич­ной за­пи­си. В конец за­пи­си (спра­ва) до­пи­сы­ва­ет­ся оста­ток от де­ле­ния суммы на 2.

3.  Преды­ду­щий пункт по­вто­ря­ет­ся для за­пи­си с до­бав­лен­ной циф­рой.

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

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

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

2.  Сумма цифр дво­ич­ной за­пи­си 3, оста­ток от де­ле­ния на 2 равен 1, новая за­пись 11011.

3.  Сумма цифр по­лу­чен­ной за­пи­си  — 4, оста­ток от де­ле­ния на 2 равен 0, новая за­пись: 110110.

4.  На экран вы­во­дит­ся число 54.

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

Ис­пол­ни­тель Цапля дей­ству­ет на плос­ко­сти с де­кар­то­вой си­сте­мой ко­ор­ди­нат. В на­чаль­ный мо­мент Цапля на­хо­дит­ся в на­ча­ле ко­ор­ди­нат, её клюв на­прав­лен вдоль по­ло­жи­тель­но­го на­прав­ле­ния оси ор­ди­нат, клюв опу­щен. При опу­щен­ном клюве Цапля остав­ля­ет на поле след в виде линии. В каж­дый кон­крет­ный мо­мент из­вест­но по­ло­же­ние ис­пол­ни­те­ля и на­прав­ле­ние его дви­же­ния. У ис­пол­ни­те­ля су­ще­ству­ет три ко­ман­ды: Вперёд 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].

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

Фо­то­гра­фию от­ска­ни­ро­ва­ли с раз­ре­ше­ни­ем 150 dpi и сжали изоб­ра­же­ние на 40%. В ре­зуль­та­те по­лу­чил­ся файл раз­ме­ром 6 Мбайт. Затем ту же фо­то­гра­фию от­ска­ни­ро­ва­ли в том же цве­то­вом ре­жи­ме с раз­ре­ше­ни­ем 300 dpi. На сколь­ко про­цен­тов не­об­хо­ди­мо сжать по­лу­чен­ное изоб­ра­же­ние, чтобы раз­мер файла со­ста­вил 12 Мбайт? За­го­лов­ки и дру­гую слу­жеб­ную ин­фор­ма­цию не учи­ты­вать. В от­ве­те за­пи­ши­те число  — округлённый до це­ло­го про­цент сжа­тия. Знак про­цен­та пи­сать не нужно.

Пётр со­став­ля­ет таб­ли­цу ко­до­вых слов для пе­ре­да­чи со­об­ще­ний, каж­до­му со­об­ще­нию со­от­вет­ству­ет своё ко­до­вое слово. В ка­че­стве ко­до­вых слов Пётр ис­поль­зу­ет все пя­ти­бук­вен­ные слова в ал­фа­ви­те {A, B, C, D, E, F}, удо­вле­тво­ря­ю­щие та­ко­му усло­вию: ко­до­вое слово не может на­чи­нать­ся с буквы F и за­кан­чи­вать­ся бук­вой A. Сколь­ко раз­лич­ных ко­до­вых слов может ис­поль­зо­вать Пётр?

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

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

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 15 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы из 8-⁠сим­воль­но­го на­бо­ра: А, В, C, D, Е, F, G, H. В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Кроме соб­ствен­но па­ро­ля для каж­до­го поль­зо­ва­те­ля в си­сте­ме хра­нят­ся до­пол­ни­тель­ные све­де­ния, для чего вы­де­ле­но целое число байт, одно и то же для всех поль­зо­ва­те­лей. Для хра­не­ния све­де­ний о 20 поль­зо­ва­те­лях по­тре­бо­ва­лось 320 байт. Сколь­ко байт вы­де­ле­но для хра­не­ния до­пол­ни­тель­ных све­де­ний об одном поль­зо­ва­те­ле? В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство байт.

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

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

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

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

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

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

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

НА­ЧА­ЛО

  ПОКА на­шлось (52) ИЛИ на­шлось (1122) ИЛИ на­шлось (2222)

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

          ТО за­ме­нить (52, 11)

     КОНЕЦ ЕСЛИ

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

          ТО за­ме­нить (2222, 5)

     КОНЕЦ ЕСЛИ

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

          ТО за­ме­нить (1122, 25)

     КОНЕЦ ЕСЛИ

  КОНЕЦ ПОКА

КОНЕЦ

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

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

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

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

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

Для ка­ко­го наи­боль­ше­го це­ло­го не­от­ри­ца­тель­но­го числа А вы­ра­же­ние

тож­де­ствен­но ис­тин­но, то есть при­ни­ма­ет зна­че­ние 1 при любых целых не­от­ри­ца­тель­ных x и y?

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

F(n)  =  2 при n ≤ 2;

F(n)  =  3 · F(n − 1) − F(n − 2) при n> 2.

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

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел. Её эле­мен­ты могут при­ни­мать целые зна­че­ния от −100 000 до 100 000

вклю­чи­тель­но.

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

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

Ответ:

Квад­рат раз­ли­но­ван на N × N кле­ток Ис­пол­ни­тель Робот может пе­ре­ме­щать­ся по клет­кам, вы­пол­няя за одно пе­ре­ме­ще­ние одну из двух ко­манд: впра­во или вниз. По ко­ман­де впра­во Робот пе­ре­ме­ща­ет­ся в со­сед­нюю пра­вую клет­ку, по ко­ман­де вниз  — в со­сед­нюю ниж­нюю.

Квад­рат огра­ни­чен внеш­ни­ми сте­на­ми. Между со­сед­ни­ми клет­ка­ми квад­ра­та также могут быть внут­рен­ние стены. Сквозь стену Робот прой­ти не может.

Перед каж­дым за­пус­ком Ро­бо­та в каж­дой клет­ке квад­ра­та лежит мо­не­та до­сто­ин­ством от 1 до 100. По­се­тив клет­ку, Робот за­би­ра­ет мо­не­ту с собой; это также от­но­сит­ся к на­чаль­ной и ко­неч­ной клет­кам марш­ру­та Ро­бо­та. В «уг­ло­вых» клет­ках поля  — тех, ко­то­рые спра­ва и снизу огра­ни­че­ны сте­на­ми, Робот не может про­дол­жать дви­же­ние, по­это­му на­коп­лен­ная сумма счи­та­ет­ся ито­го­вой. Таких ко­неч­ных кле­ток на поле может быть не­сколь­ко, вклю­чая пра­вую ниж­нюю клет­ку поля. При раз­ных за­пус­ках ито­го­вые на­коп­лен­ные суммы могут раз­ли­чать­ся.

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

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

Для та­ко­го ла­би­рин­та ответ будет 42 16.

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

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

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

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

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

Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся более 200. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 201 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней; 1 ≤ S ≤ 200.

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

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

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

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

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

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

Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся более 200. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 201 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней; 1 ≤ S ≤ 200.

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

Най­ди­те ми­ни­маль­ное зна­че­ние 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, то про­грам­ма 212 по­сле­до­ва­тель­но пре­об­ра­зу­ет его в 2, 3, 6.

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

Тек­сто­вый файл со­дер­жит стро­ки раз­лич­ной длины, со­дер­жа­щие толь­ко за­глав­ные буквы ла­тин­ско­го ал­фа­ви­та (ABC Z). Будем на­зы­вать це­поч­кой груп­пу иду­щих под­ряд оди­на­ко­вых букв в одной стро­ке. Опре­де­ли­те, сколь­ко раз буква, об­ра­зу­ю­щая самую длин­ную це­поч­ку в файле, встре­ча­ет­ся в стро­ке, со­дер­жа­щей эту це­поч­ку. Если в файле есть не­сколь­ко це­по­чек оди­на­ко­вой мак­си­маль­ной длины, нужно вы­брать ту из них, для ко­то­рой общее ко­ли­че­ство об­ра­зу­ю­щих це­поч­ку букв в со­от­вет­ству­ю­щей стро­ке будет боль­ше.

При­мер.

Пусть файл со­дер­жит такие стро­ки:

ABBAAABBABBXY

XYYYXYAB

Здесь в пер­вой стро­ке есть це­поч­ка длины 3, об­ра­зо­ван­ная бук­ва­ми A, всего буква A в этой стро­ке встре­ча­ет­ся 5 раз. Во вто­рой стро­ке тоже есть це­поч­ка длины 3, но об­ра­зу­ю­щая эту це­поч­ку буква Y встре­ча­ет­ся в этой стро­ке всего 4 раза. 5 > 4, по­это­му в от­ве­те в дан­ном слу­чае надо за­пи­сать число 5.

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

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

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

5

10 140

100 10

120 10

131 19

131 49

Ответ к при­ме­ру: 3 1.

Дана по­сле­до­ва­тель­ность целых чисел. Рас­сто­я­ние между эле­мен­та­ми по­сле­до­ва­тель­но­сти  — это раз­ность их по­ряд­ко­вых но­ме­ров. На­при­мер, если два эле­мен­та стоят в по­сле­до­ва­тель­но­сти рядом, рас­сто­я­ние между ними равно 1, если два эле­мен­та стоят через один  — рас­сто­я­ние равно 2 и так далее.

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

За­пи­ши­те в от­ве­те най­ден­ную сумму.

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число K  — па­ра­метр для опре­де­ле­ния рас­сто­я­ния, вто­рая стро­ка со­дер­жит число N  — общее ко­ли­че­ство чисел в на­бо­ре (1 < 2K < N). Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее по мо­ду­лю 10⁷.

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число K  — па­ра­метр для опре­де­ле­ния рас­сто­я­ния, вто­рая стро­ка со­дер­жит число N  — общее ко­ли­че­ство чисел в на­бо­ре (1  < 3K < N). Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее по мо­ду­лю 10⁷.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла тре­бу­е­мую сумму для файла A, затем  — для файла B.

Ответ: