На ри­сун­ке схема дорог изоб­ра­же­на в виде графа, в таб­ли­це звёздоч­ка­ми обо­зна­че­но на­ли­чие до­ро­ги между населёнными пунк­та­ми. Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Вы­пи­ши­те по­сле­до­ва­тель­но без про­бе­лов и зна­ков пре­пи­на­ния ука­зан­ные на графе бук­вен­ные обо­зна­че­ния пунк­тов от П1 до П9: сна­ча­ла букву, со­от­вет­ству­ю­щую П1, затем букву, со­от­вет­ству­ю­щую П2, и т. д.

Ло­ги­че­ская функ­ция F задаётся вы­ра­же­ни­ем:

Дан ча­стич­но за­пол­нен­ный фраг­мент, со­дер­жа­щий не­по­вто­ря­ю­щи­е­ся стро­ки таб­ли­цы ис­тин­но­сти функ­ции F.

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

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

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

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

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся шиф­ро­ван­ные со­об­ще­ния, со­дер­жа­щие толь­ко де­сять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для пе­ре­да­чи ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код. Для де­вя­ти букв ис­поль­зу­ют­ся ко­до­вые слова.

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

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

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

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

2.  В конец дво­ич­ной за­пи­си до­бав­ля­ет­ся дво­ич­ный код остат­ка от де­ле­ния числа N на 4.

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

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

1.  Стро­им дво­ич­ную за­пись: 13₁₀  =  1101₂.

2.  Оста­ток от де­ле­ния 13 на 4 равен 1, до­бав­ля­ем к дво­ич­ной за­пи­си цифру 1, по­лу­ча­ем 11011₂  =  27₁₀.

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

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

1.  Стро­им дво­ич­ную за­пись: 14₁₀  =  1110₂.

2.  Оста­ток от де­ле­ния 14 на 4 равен 2, до­бав­ля­ем к дво­ич­ной за­пи­си цифры 10 (10₂  =  2₁₀), по­лу­ча­ем 111010₂  =  58₁₀.

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

Назовём до­ступ­ны­ми числа, ко­то­рые могут по­лу­чить­ся в ре­зуль­та­те ра­бо­ты этого ал­го­рит­ма. На­при­мер, числа 27 и 58  — до­ступ­ные. Опре­де­ли­те ко­ли­че­ство до­ступ­ных чисел, при­над­ле­жа­щих от­рез­ку [1 000 000 000; 1 789 456 123].

Ис­пол­ни­тель Че­ре­па­ха дей­ству­ет на плос­ко­сти с де­кар­то­вой си­сте­мой ко­ор­ди­нат. В на­чаль­ный мо­мент Че­ре­па­ха на­хо­дит­ся B на­ча­ле ко­ор­ди­нат, её го­ло­ва на­прав­ле­на вдоль по­ло­жи­тель­но­го на­прав­ле­ния оси ор­ди­нат, хвост опу­щен. При опу­щен­ном хво­сте Че­ре­па­ха остав­ля­ет на поле след в виде линии. В каж­дый кон­крет­ный мо­мент из­вест­но по­ло­же­ние ис­пол­ни­те­ля и на­прав­ле­ние его дви­же­ния. У ис­пол­ни­те­ля су­ще­ству­ет 6 ко­манд: Под­нять хвост, озна­ча­ю­щая пе­ре­ход к пе­ре­ме­ще­нию 6eз ри­со­ва­ния; Опу­стить хвост, озна­ча­ю­щая пе­ре­ход в режим ри­со­ва­ния; Вперёд n (где n  — целое число), вы­зы­ва­ю­щая пе­ре­дви­же­ние Че­ре­па­хи на n еди­ниц в том на­прав­ле­нии, куда ука­зы­ва­ет её го­ло­ва; Назад n (где n  — целое число), вы­зы­ва­ю­щая пе­ре­дви­же­ние в про­ти­во­по­лож­ном го­ло­ве на­прав­ле­нии; На­пра­во m (где m  — целое число), вы­зы­ва­ю­щая из­ме­не­ние на­прав­ле­ния дви­же­ния на m гра­ду­сов по ча­со­вой стрел­ке, На­ле­во m (где m  — целое число), вы­зы­ва­ю­щая из­ме­не­ние на­прав­ле­ния дви­же­ния на m гра­ду­сов про­тив ча­со­вой стрел­ки. За­пись По­вто­ри k [Ко­ман­да1 Ко­ман­да2 ... Ко­ман­даS] озна­ча­ет, что по­сле­до­ва­тель­ность из S ко­манд по­вто­рит­ся k раз.

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

По­вто­ри 4 [Вперёд 10 На­пра­во 270]

Под­нять хвост

Вперёд 3 На­пра­во 270 Вперёд 5 На­пра­во 90

Опу­стить хвост

По­вто­ри 2 [Вперёд 10 На­пра­во 270 Вперёд 12 На­пра­во 270].

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

Ка­ме­ра на­блю­де­ния сни­ма­ет видео с ча­сто­той n кад­ров в се­кун­ду (n  — целое число) и пе­ре­даёт его по ка­на­лу с про­пуск­ной спо­соб­но­стью 750 Кбайт/⁠сек. Видео сни­ма­ет­ся с раз­ре­ше­ни­ем 1024 × 768 пик­се­лей и па­лит­рой 256 цве­тов, при этом ис­поль­зу­ют­ся ме­то­ды сжа­тия, поз­во­ля­ю­щие умень­шить раз­мер изоб­ра­же­ния в сред­нем на 85%. Опре­де­ли­те мак­си­маль­но воз­мож­ное зна­че­ние n, при ко­то­ром воз­мож­на пе­ре­да­ча в ре­жи­ме ре­аль­но­го вре­ме­ни.

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

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

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

—  наи­мень­шее из четырёх чисел более чем в шесть раз мень­ше суммы трёх дру­гих;

—  про­из­ве­де­ние наи­боль­ше­го и наи­мень­ше­го числа боль­ше про­из­ве­де­ния остав­ших­ся чисел.

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

Текст про­из­ве­де­ния Льва Ни­ко­ла­е­ви­ча Тол­сто­го «Се­ва­сто­поль­ские рас­ска­зы» пред­став­лен в виде фай­лов раз­лич­ных фор­ма­тов. От­крой­те один из фай­лов и опре­де­ли­те, сколь­ко раз встре­ча­ет­ся в тек­сте от­дель­ное слово «те­перь» со строч­ной буквы. Дру­гие формы этого слова учи­ты­вать не сле­ду­ет. В от­ве­те за­пи­ши­те толь­ко число.

В ин­фор­ма­ци­он­ной си­сте­ме хра­нит­ся ин­фор­ма­ция об объ­ек­тах опре­делённой струк­ту­ры. Каж­дый объ­ект опи­сы­ва­ет­ся как по­сле­до­ва­тель­ность бло­ков. Для каж­до­го блока ука­зы­ва­ют­ся его код и тип. Код блока со­сто­ит из 6 сим­во­лов, каж­дый из ко­то­рых может быть за­глав­ной или строч­ной ла­тин­ской бук­вой. Каж­дый сим­вол кода ко­ди­ру­ет­ся ми­ни­маль­но воз­мож­ным ко­ли­че­ством битов. Тип блока  — это целое число от 1 до N, ко­то­рое ко­ди­ру­ет­ся ми­ни­маль­но воз­мож­ным ко­ли­че­ством битов. Блок в целом ко­ди­ру­ет­ся ми­ни­маль­но воз­мож­ным целым ко­ли­че­ством бай­тов.

Для хра­не­ния ин­фор­ма­ции о каж­дом объ­ек­те вы­де­ля­ет­ся оди­на­ко­вое для всех объ­ек­тов ми­ни­маль­ное ко­ли­че­ство бай­тов, до­ста­точ­ное для опи­са­ния 40 бло­ков.

Из­вест­но, что для хра­не­ния дан­ных о 2048 объ­ек­тах по­тре­бо­ва­лось 480 Кбайт. Опре­де­ли­те мак­си­маль­но воз­мож­ное зна­че­ние ко­ли­че­ства раз­лич­ных типов бло­ков N.

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

λ

λ

...

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

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

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

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

На месте пре­ступ­ле­ния были об­на­ру­же­ны че­ты­ре об­рыв­ка бу­ма­ги. След­ствие уста­но­ви­ло, что на них за­пи­са­ны фраг­мен­ты од­но­го 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. Назовём трой­кой три иду­щих под­ряд эле­мен­та по­сле­до­ва­тель­но­сти.

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

—  оста­ток от де­ле­ния на 3 ровно од­но­го числа из трой­ки равен остат­ку от де­ле­ния на 3 ми­ни­маль­но­го эле­мен­та всей по­сле­до­ва­тель­но­сти;

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

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

Ответ:

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

За один ход робот может пе­ре­ме­стить­ся на одну клет­ку впра­во или на одну клет­ку вниз. Клет­ка, из ко­то­рой робот не может сде­лать до­пу­сти­мо­го хода (спра­ва и снизу на­хо­дят­ся гра­ни­цы поля или за­прещённые клет­ки), на­зы­ва­ет­ся фи­наль­ной. На поле может быть не­сколь­ко фи­наль­ных кле­ток.

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

За­да­ние 1.  Опре­де­ли­те ми­ни­маль­ный на­чаль­ный запас энер­гии, ко­то­рый поз­во­лит ро­бо­ту до­брать­ся до любой фи­наль­ной клет­ки.

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

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це. В от­ве­те за­пи­ши­те два числа: сна­ча­ла ответ на за­да­ние 1, затем ответ на за­да­ние 2.

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

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

В на­чаль­ный мо­мент в куче было S кам­ней, 1 < S < 99.

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

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

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

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

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

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

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

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

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

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

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

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

В на­чаль­ный мо­мент в куче было S кам­ней, 1 < S < 99.

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

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

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

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

Тек­сто­вый файл со­дер­жит стро­ки раз­лич­ной длины, со­дер­жа­щие толь­ко за­глав­ные буквы ла­тин­ско­го ал­фа­ви­та (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.

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

Будем на­зы­вать цен­тром кла­сте­ра точку этого кла­сте­ра, сумма рас­сто­я­ний от ко­то­рой до всех осталь­ных точек кла­сте­ра ми­ни­маль­на. Для каж­до­го кла­сте­ра га­ран­ти­ру­ет­ся един­ствен­ность его цен­тра. Рас­сто­я­ние между двумя точ­ка­ми на плос­ко­сти и вы­чис­ля­ет­ся по фор­му­ле:

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

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

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

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

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

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

Ответ: