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

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

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

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

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

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

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

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

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

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

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

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

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

Все за­глав­ные буквы рус­ско­го ал­фа­ви­та за­ко­ди­ро­ва­ны не­рав­но­мер­ным дво­ич­ным кодом, в ко­то­ром ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это усло­вие обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: Г  — 11, И  — 000, К  — 1011, Р  — 001. Из­вест­но также, что код слова ГРАМ­МА­ТИ­КА со­дер­жит 29 дво­ич­ных зна­ков. Ука­жи­те воз­мож­ный код ми­ни­маль­ной длины для буквы М. Если таких кодов не­сколь­ко, ука­жи­те тот из них, ко­то­рый имеет ми­ни­маль­ное чис­ло­вое зна­че­ние.

На вход ал­го­рит­ма подаётся на­ту­раль­ное число 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 гра­ду­сов по ча­со­вой стрел­ке. За­пись По­вто­ри k [Ко­ман­да1 Ко­ман­да2 … Ко­ман­даS] озна­ча­ет, что по­сле­до­ва­тель­ность из S ко­манд по­вто­рит­ся k раз. Че­ре­па­хе был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм: По­вто­ри 6 [На­пра­во 36 Вперёд 10 На­пра­во 36].

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

Му­зы­каль­ный фраг­мент был за­пи­сан в фор­ма­те сте­рео (двух­ка­наль­ная за­пись), оциф­ро­ван с ча­сто­той дис­кре­ти­за­ции 44 кГц и раз­ре­ше­ни­ем 16 бит и со­хранён без ис­поль­зо­ва­ния сжа­тия дан­ных. По­лу­чил­ся файл раз­ме­ром 120 Мбайт. Затем тот же фраг­мент был за­пи­сан в фор­ма­те квад­ро (четырёхка­наль­ная за­пись) с ча­сто­той дис­кре­ти­за­ции 88 кГц и тоже со­хранён без сжа­тия, при этом по­лу­чил­ся файл раз­ме­ром 720 Мбайт. С каким раз­ре­ше­ни­ем про­во­ди­лась вто­рая за­пись? В от­ве­те ука­жи­те целое число  — раз­ре­ше­ние в битах, еди­ни­цу из­ме­ре­ния пи­сать не нужно.

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

1.  НННН

2.  НННР

3.  НННТ

4.  НННУ

5.  ННРН

За­пи­ши­те слово, ко­то­рое стоит на 215-⁠м месте от на­ча­ла спис­ка.

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

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

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

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

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

Опре­де­ли­те, сколь­ко раз в тек­сте про­из­ве­де­ния А. С. Гри­бо­едо­ва «Горе от ума», не счи­тая сно­сок, встре­ча­ет­ся слово «ба­тюш­ка» или «Ба­тюш­ка». Дру­гие формы слова «ба­тюш­ка», такие как «ба­тюш­ке», «ба­тюш­ки» и т. д., учи­ты­вать не сле­ду­ет. В от­ве­те ука­жи­те толь­ко число.

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

Опре­де­ли­те объём па­мя­ти (в Кбайт), не­об­хо­ди­мый для хра­не­ния 65 536 иден­ти­фи­ка­то­ров. В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство Кбайт.

Ис­пол­ни­тель МТ пред­став­ля­ет собой чи­та­ю­щую и за­пи­сы­ва­ю­щую го­лов­ку, ко­то­рая может пе­ре­дви­гать­ся вдоль бес­ко­неч­ной го­ри­зон­таль­ной ленты, раз­делённой на рав­ные ячей­ки. В каж­дой ячей­ке на­хо­дит­ся ровно один сим­вол из ал­фа­ви­та ис­пол­ни­те­ля (мно­же­ство сим­во­лов A  =  {a₀, a₁, ..., a_n − 1}), вклю­чая спе­ци­аль­ный пу­стой сим­вол a₀.

Время ра­бо­ты ис­пол­ни­те­ля де­лит­ся на дис­крет­ные такты (шаги). На каж­дом такте го­лов­ка МТ на­хо­дит­ся в одном из мно­же­ства до­пу­сти­мых со­сто­я­ний Q  =  {q₀, q₁, ..., q_n − 1}. В на­чаль­ный мо­мент вре­ме­ни го­лов­ка на­хо­дит­ся в на­чаль­ном со­сто­я­нии q₀.

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

Про­грам­ма ра­бо­ты ис­пол­ни­те­ля МТ задаётся в таб­лич­ном виде.

В пер­вой стро­ке пе­ре­чис­ле­ны все воз­мож­ные сим­во­лы в те­ку­щей ячей­ке ленты, в пер­вом столб­це  — воз­мож­ные со­сто­я­ния го­лов­ки. На пе­ре­се­че­нии i⁠-й стро­ки и j⁠-го столб­ца на­хо­дит­ся ко­ман­да, ко­то­рую вы­пол­ня­ет МТ, когда го­лов­ка обо­зре­ва­ет j⁠-й сим­вол, на­хо­дясь в i⁠-м со­сто­я­нии. Если пара «сим­вол  — со­сто­я­ние» не­воз­мож­на, то клет­ка для ко­ман­ды остаётся пу­стой.

Каж­дая ко­ман­да со­сто­ит из трёх эле­мен­тов, раз­делённых за­пя­ты­ми: пер­вый эле­мент  — за­пи­сы­ва­е­мый в те­ку­щую ячей­ку сим­вол ал­фа­ви­та (может сов­па­дать с тем, ко­то­рый там уже за­пи­сан). Вто­рой эле­мент  — один из четырёх сим­во­лов «L», «R», «N», «S». Сим­во­лы «L» и «R» озна­ча­ют сдвиг в левую или пра­вую ячей­ки со­от­вет­ствен­но, «N»  — от­сут­ствие сдви­га, «S»  — за­вер­ше­ние ра­бо­ты ис­пол­ни­те­ля МТ после вы­пол­не­ния те­ку­щей ко­ман­ды.

Сдвиг про­ис­хо­дит после за­пи­си сим­во­ла в те­ку­щую ячей­ку. Тре­тий эле­мент  — новое со­сто­я­ние го­лов­ки после вы­пол­не­ния ко­ман­ды.

На­при­мер, ко­ман­да 0, L, q3 вы­пол­ня­ет­ся сле­ду­ю­щим об­ра­зом: в те­ку­щую ячей­ку за­пи­сы­ва­ет­ся сим­вол «0», затем го­лов­ка сдви­га­ет­ся в со­сед­нюю слева ячей­ку и пе­ре­хо­дит в со­сто­я­ние q3.

При­ведём при­мер вы­пол­не­ния про­грам­мы, за­дан­ной таб­лич­но. На ленте за­пи­са­но не­из­вест­ное не­ну­ле­вое ко­ли­че­ство рас­по­ло­жен­ных под­ряд в со­сед­них ячей­ках сим­во­лов «Z», все осталь­ные ячей­ки ленты за­пол­не­ны пу­стым сим­во­лом «λ». В на­чаль­ный мо­мент вре­ме­ни го­лов­ка на­хо­дит­ся на не­из­вест­ном не­ну­ле­вом рас­сто­я­нии спра­ва от са­мо­го пра­во­го сим­во­ла «Z».

Про­грам­ма.

за­ме­ня­ет на ленте все сим­во­лы «Z» на «X» и оста­нав­ли­ва­ет ис­пол­ни­те­ля в пер­вой ячей­ке слева от по­сле­до­ва­тель­но­сти сим­во­лов «X».

Воз­мож­ное на­чаль­ное со­сто­я­ние ис­пол­ни­те­ля.

...

λ

λ

Z

Z

Z

Z

λ

...

Ко­неч­но со­сто­я­ние ис­пол­ни­те­ля после за­вер­ше­ния вы­пол­не­ния про­грам­мы.

...

λ

X

X

X

X

λ

λ

...

Вы­пол­ни­те за­да­ние.

На ленте в со­сед­них ячей­ках за­пи­са­на по­сле­до­ва­тель­ность из 1200 сим­во­лов, вклю­ча­ю­щая толь­ко нули и еди­ни­цы. Ячей­ки спра­ва и слева от по­сле­до­ва­тель­но­сти за­пол­не­ны пу­сты­ми сим­во­ла­ми «λ». В на­чаль­ный мо­мент вре­ме­ни го­лов­ка рас­по­ло­же­на в бли­жай­шей ячей­ке спра­ва от по­сле­до­ва­тель­но­сти.

Про­грам­ма ра­бо­ты ис­пол­ни­те­ля.

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

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

Числа M и N за­пи­са­ны в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 9 со­от­вет­ствен­но.

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

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

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

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

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

F(a, 0)  =  a;

F(a, b)  =  F(a−b, b), если a ≥ b > 0;

F(a, b)  =  F(b, a), если a < b.

Ука­жи­те ко­ли­че­ство таких чисел n из ин­тер­ва­ла

для ко­то­рых F(n, 14)  =  1.

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

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

—  за­пись эле­мен­тов пары за­кан­чи­ва­ет­ся одной и той же циф­рой;

—  ровно один эле­мент из пары де­лит­ся без остат­ка на 7;

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

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

Ответ:

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

На каж­дый шаг впра­во робот за­тра­чи­ва­ет 15 еди­ниц энер­гии, на шаг вниз  — 20 еди­ниц, на шаг по диа­го­на­ли  — 10 еди­ниц. В каж­дой клет­ке, вклю­чая на­чаль­ную и ко­неч­ную, робот по­пол­ня­ет запас энер­гии на ве­ли­чи­ну, рав­ную за­пи­сан­но­му в этой клет­ке числу. В на­чаль­ный мо­мент (до под­за­ряд­ки в на­чаль­ной клет­ке) запас энер­гии ро­бо­та равен нулю.

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

В от­ве­те за­пи­ши­те два числа: сна­ча­ла мак­си­маль­но воз­мож­ное зна­че­ние, затем ми­ни­маль­но воз­мож­ное.

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

При ука­зан­ных вход­ных дан­ных мак­си­маль­ное зна­че­ние 303 по­лу­чит­ся при дви­же­нии по марш­ру­ту 43 → 49 → 52 → 83 → 22 → 85 →R 9; 74, а ми­ни­маль­ное зна­че­ние 141 при дви­же­нии по марш­ру­ту 43 → 49 → 8 → 22 → 74. В от­ве­те в дан­ном слу­чае надо за­пи­сать числа 303 и 141.

Ответ:

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

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

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

Будем го­во­рить, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка.

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

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

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

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

Будем го­во­рить, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка.

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

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

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

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

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

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

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

Будем го­во­рить, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка.

Най­ди­те ми­ни­маль­ное зна­че­ние 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 ре­зуль­та­том яв­ля­ет­ся число 20 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 10?

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

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов ла­тин­ско­го ал­фа­ви­та. Опре­де­ли­те длину ми­ни­маль­ной под­стро­ки, со­дер­жа­щую не менее 130 сим­во­лов W. Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му.

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

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

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

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

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

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

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

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

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

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

4

3

10

15

35

20

5

10

45

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

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

Ответ:

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

Даны два вход­ных файла (файл 27A и файл 27Б). В файле 27A хра­нят­ся дан­ные о звёздах двух кла­сте­ров. В каж­дой стро­ке за­пи­са­на ин­фор­ма­ция о рас­по­ло­же­нии на карте одной звез­ды: ко­ор­ди­на­та x, затем ко­ор­ди­на­та y (в услов­ных еди­ни­цах). Из­вест­но, что ко­ли­че­ство звёзд не пре­вы­ша­ет 1000. В файле 27Б хра­нят­ся дан­ные о звёздах трёх кла­сте­ров.

Из­вест­но, что ко­ли­че­ство звёзд не пре­вы­ша­ет 10 000. Струк­ту­ра хра­не­ния ин­фор­ма­ции о звез­дах в файле 27Б ана­ло­гич­на файлу 27А. Воз­мож­ные дан­ные од­но­го из фай­лов ил­лю­стри­ро­ва­ны гра­фи­ком.

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

Ответ: