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

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

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

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

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

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

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

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

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

Таб­ли­ца «Ма­га­зин» со­дер­жит ин­фор­ма­цию о ме­сто­на­хож­де­нии ма­га­зи­нов. За­го­ло­вок таб­ли­цы имеет сле­ду­ю­щий вид.

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

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

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

Для ко­ди­ро­ва­ния по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв К, О, Л, Б, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Букве К со­от­вет­ству­ет дво­ич­ный код 0, букве О  — код 10.

Ка­ко­ва наи­мень­шая сум­мар­ная длина ко­до­вых слов для всех букв в слове КО­ЛО­БОК?

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

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

2.  К этой за­пи­си до­пи­сы­ва­ют­ся спра­ва ещё два раз­ря­да по сле­ду­ю­ще­му пра­ви­лу:

а)  скла­ды­ва­ют­ся все цифры дво­ич­ной за­пи­си числа N, и оста­ток от де­ле­ния суммы на 2 до­пи­сы­ва­ет­ся в конец числа (спра­ва). На­при­мер, за­пись 11100 пре­об­ра­зу­ет­ся в за­пись 111001;

б)  над этой за­пи­сью про­из­во­дят­ся те же дей­ствия  — спра­ва до­пи­сы­ва­ет­ся оста­ток от де­ле­ния суммы её цифр на 2.

По­лу­чен­ная таким об­ра­зом за­пись (в ней на два раз­ря­да боль­ше, чем в за­пи­си ис­ход­но­го числа N) яв­ля­ет­ся дво­ич­ной за­пи­сью ис­ко­мо­го числа R.

На­при­мер, для ис­ход­но­го числа 12₁₀  =  1100₂ ре­зуль­та­том яв­ля­ет­ся число 110000₂  =  48₁₀, а для ис­ход­но­го числа 7₁₀  =  111₂ это число 11110₂  =  30₁₀.

Ука­жи­те такое наи­мень­шее число N, для ко­то­ро­го ре­зуль­тат ра­бо­ты ал­го­рит­ма боль­ше числа 253.

В от­ве­те за­пи­ши­те это число в де­ся­тич­ной си­сте­ме счис­ле­ния.

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

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

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

На­пра­во 45 По­вто­ри 7 [Вперёд 5 На­пра­во 45 Вперёд 10 На­пра­во 135].

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

Лена за­пи­сы­ва­ет го­ло­со­вое со­об­ще­ние для своей по­дру­ги. Перед от­прав­кой со­об­ще­ние оциф­ро­вы­ва­ет­ся в фор­ма­те сте­рео с ча­сто­той дис­кре­ти­за­ции 28 000 Гц и глу­би­ной ко­ди­ро­ва­ния 8 бит. Опре­де­ли­те наи­мень­шее ко­ли­че­ство Кбайт, не­об­хо­ди­мое для со­хра­не­ния со­об­ще­ния в па­мя­ти (без учёта за­го­лов­ка), если его дли­тель­ность  — 2 ми­ну­ты 20 се­кунд.

В от­ве­те ука­жи­те толь­ко число.

Игорь со­став­ля­ет пя­ти­знач­ные числа, ис­поль­зуя цифры де­вя­те­рич­ной си­сте­мы счис­ле­ния. Сколь­ко раз­лич­ных чисел может со­ста­вить Игорь, в ко­то­рых ровно две цифры 3 и нечётные цифры не стоят рядом с циф­рой 2?

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

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

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

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

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

С по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз в тек­сте глав 5 и 6 ро­ма­на в сти­хах А. С. Пуш­ки­на «Ев­ге­ний Оне­гин» встре­ча­ет­ся слово «Что» (или «что») в ка­че­стве от­дель­но­го слова.

Ре­гистр при по­ис­ке учи­ты­вать не сле­ду­ет, дру­гие слова, в со­став ко­то­рых вхо­дит «что» как часть, учи­ты­вать не нужно. В от­ве­те за­пи­ши­те толь­ко число.

На пред­при­я­тии каж­дой из­го­тов­лен­ной де­та­ли при­сва­и­ва­ют се­рий­ный номер из 225 сим­во­лов. Для хра­не­ния каж­до­го но­ме­ра от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное число байт; ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние  — все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным чис­лом бит. Из­вест­но, что для хра­не­ния 1270 се­рий­ных но­ме­ров от­ве­де­но не более 104 Кбайт па­мя­ти.

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

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

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

Про­грам­ма

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

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

...

λ

λ

Z

Z

Z

Z

λ

...

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

...

λ

X

X

X

X

λ

λ

...

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

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

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

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

В тер­ми­но­ло­гии сетей TCP/⁠IP мас­кой сети на­зы­ва­ют дво­ич­ное число, ко­то­рое по­ка­зы­ва­ет, какая часть IP-⁠ад­ре­са узла сети от­но­сит­ся к ад­ре­су сети, а какая  — к ад­ре­су узла в этой сети. Адрес сети по­лу­ча­ет­ся в ре­зуль­та­те при­ме­не­ния по­раз­ряд­ной конъ­юнк­ции к за­дан­но­му ад­ре­су узла и его маске.

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

Адрес сети и ши­ро­ко­ве­ща­тель­ный адрес не могут быть ис­поль­зо­ва­ны для ад­ре­са­ции се­те­вых устройств.

Сеть за­да­на IP-⁠ад­ре­сом од­но­го из вхо­дя­щих в нее узлов 102.162.200.51 и се­те­вой мас­кой 255.255.255.0.

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

На­при­мер, если бы най­ден­ный адрес был равен 100.20.3.4, то в от­ве­те сле­до­ва­ло бы за­пи­сать: 127.

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

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

Обо­зна­чим через ДЕЛ(n, m) утвер­жде­ние «на­ту­раль­ное число n де­лит­ся без остат­ка на на­ту­раль­ное число m». Задан от­ре­зок B  =  [15; 30]. Для ка­ко­го наи­боль­ше­го на­ту­раль­но­го числа A фор­му­ла

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

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

если

если

Опре­де­ли­те зна­че­ние В от­ве­те за­пи­ши­те целую часть.

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел.

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

Ответ:

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

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

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

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

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

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

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

—  до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) 4 камня;

—  уве­ли­чить ко­ли­че­ство кам­ней в одной из куч (по сво­е­му вы­бо­ру) в 2 раза.

На­при­мер, пусть в одной куче 20 кам­ней, а в дру­гой 30 кам­ней; такую по­зи­цию в игре обо­зна­чим (20, 30). Тогда за один ход можно по­лу­чить любую из четырёх по­зи­ций: (24, 30), (20, 34), (60, 30), (20, 90).

Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. Игра за­вер­ша­ет­ся в тот мо­мент, когда сум­мар­ное ко­ли­че­ство кам­ней в двух кучах ста­но­вит­ся не менее 154. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший такую иг­ро­вую по­зи­цию, при ко­то­рой в двух кучах сум­мар­но 154 камня или боль­ше. В на­чаль­ный мо­мент в пер­вой куче 11 кам­ней, во вто­рой куче  — S кам­ней;

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

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

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

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

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

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

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

—  у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети;

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

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

При­оста­нов­ка вы­пол­не­ния про­цес­са не до­пус­ка­ет­ся. Будем го­во­рить, что про­цесс B за­ви­сит от про­цес­са A, если для вы­пол­не­ния про­цес­са B не­об­хо­ди­мы ре­зуль­та­ты вы­пол­не­ния про­цес­са A. В этом слу­чае про­цес­сы A и B могут вы­пол­нять­ся толь­ко по­сле­до­ва­тель­но.

Общее время окон­ча­ния ра­бо­ты всех про­цес­сов ми­ни­маль­но.

Ин­фор­ма­ция о про­цес­сах пред­став­ле­на в файле в виде таб­ли­цы. В пер­вом столб­це таб­ли­цы ука­зан иден­ти­фи­ка­тор про­цес­са (ID), во вто­ром столб­це таб­ли­цы  — время его вы­пол­не­ния в мил­ли­се­кун­дах, в тре­тьем столб­це пе­ре­чис­ле­ны с раз­де­ли­те­лем «;» ID про­цес­сов, от ко­то­рых за­ви­сит дан­ный про­цесс. Если про­цесс не­за­ви­си­мый, то в таб­ли­це ука­за­но зна­че­ние 0.

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

Опре­де­ли­те мак­си­маль­ное ко­ли­че­ство про­цес­сов, ко­то­рые нач­нут вы­пол­нять­ся не ранее 15-⁠й се­кун­ды (время на­ча­ла 15 се­кунд также учи­ты­ва­ет­ся).

Для при­ведённой таб­ли­цы про­цесс 3 на­чи­на­ет­ся на 8-⁠й мс, за­кан­чи­ва­ет­ся на 9-⁠й мс.

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

Вы­пол­ни­те за­да­ния, ис­поль­зуя дан­ные из файла ниже:

Ис­пол­ни­тель Робот пре­об­ра­зу­ет число, за­пи­сан­ное на экра­не. У ис­пол­ни­те­ля есть две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

1.  При­бавь 1;

2.  По­ме­нять цифры в раз­ря­де еди­ниц и де­сят­ков ме­ста­ми, если раз­ряд де­сят­ков мень­ше раз­ря­да еди­ниц.

Сколь­ко есть про­грамм, ко­то­рые пре­об­ра­зу­ют число 100 в число 150?

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов и со­дер­жит толь­ко де­ся­тич­ные цифры, а также знаки «+» и «*» (сло­же­ния и умно­же­ния). Опре­де­ли­те мак­си­маль­ное ко­ли­че­ство сим­во­лов в не­пре­рыв­ной по­сле­до­ва­тель­но­сти, яв­ля­ю­щей­ся кор­рект­ным ариф­ме­ти­че­ским вы­ра­же­ни­ем с це­лы­ми не­от­ри­ца­тель­ны­ми чис­ла­ми (без знака). В этом вы­ра­же­нии ни­ка­кие два знака ариф­ме­ти­че­ских опе­ра­ций не стоят рядом. В за­пи­си чисел от­сут­ству­ют не­зна­ча­щие (ве­ду­щие) нули. В от­ве­те ука­жи­те ко­ли­че­ство сим­во­лов в най­ден­ном вы­ра­же­нии.

Вход­ной файл со­дер­жит ин­фор­ма­цию о за­яв­ках граж­дан, об­ра­ща­ю­щих­ся во мно­го­функ­ци­о­наль­ный центр (МФЦ) в те­че­ние ка­лен­дар­ных суток. В за­яв­ке ука­за­ны время на­ча­ла и время окон­ча­ния приёма спе­ци­а­ли­стом (в ми­ну­тах от на­ча­ла суток). Ра­бо­чие места спе­ци­а­ли­стов МФЦ (окна) про­ну­ме­ро­ва­ны на­ту­раль­ны­ми чис­ла­ми на­чи­ная с 1. Приём од­но­го граж­да­ни­на ведёт сво­бод­ный спе­ци­а­лист в окне с ми­ни­маль­ным но­ме­ром. Новый по­се­ти­тель может об­ра­тить­ся к осво­бо­див­ше­му­ся спе­ци­а­ли­сту, на­чи­ная со сле­ду­ю­щей ми­ну­ты после за­вер­ше­ния приёма преды­ду­ще­го. Если в мо­мент об­ра­ще­ния в МФЦ сво­бод­ных спе­ци­а­ли­стов нет, то граж­да­нин ухо­дит. Опре­де­ли­те, сколь­ко граж­дан смо­жет по­пасть на приём в МФЦ в те­че­ние 24 часов, и каков номер окна спе­ци­а­ли­ста, ко­то­рый начнёт при­ни­мать по­се­ти­те­ля по­след­ним. Если таких окон не­сколь­ко, ука­жи­те наи­мень­ший номер окна.

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

Вход­ные дан­ные пред­став­ле­ны в файле сле­ду­ю­щим об­ра­зом. Пер­вая стро­ка вход­но­го файла со­дер­жит на­ту­раль­ное число K, не пре­вы­ша­ю­щее 1000,  — ко­ли­че­ство окон в МФЦ. Во вто­рой стро­ке за­пи­са­но на­ту­раль­ное число N обо­зна­ча­ю­щее ко­ли­че­ство граж­дан.

Каж­дая из сле­ду­ю­щих N строк со­дер­жит два на­ту­раль­ных числа, каж­дое из ко­то­рых не пре­вы­ша­ет 1440: ука­зан­ные в за­яв­ке время на­ча­ла и время окон­ча­ния приёма (в ми­ну­тах от на­ча­ла суток).

За­пи­ши­те в от­ве­те два числа: ко­ли­че­ство граж­дан, ко­то­рые смо­гут вос­поль­зо­вать­ся услу­га­ми МФЦ, и номер окна, в ко­то­ром спе­ци­а­лист при­мет по­след­не­го граж­да­ни­на.

Ответ:

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

В файле А хра­нят­ся дан­ные о звёздах 2-⁠х кла­сте­ров, в файле Б хра­нят­ся дан­ные о звёздах 3-⁠х кла­сте­ров. Для каж­дой звез­ды дана ха­рак­те­ри­сти­ка: тип цвета, тип све­ти­мо­сти и её раз­мер в со­от­вет­ствии с таб­ли­цей.

По­лу­чен­ные зна­че­ния за­пи­са­ны в ха­рак­те­ри­сти­ке слит­но: обо­зна­че­ние цвета, све­ти­мость (обо­зна­ча­ет­ся циф­рой 1–⁠9) и обо­зна­че­ние раз­ме­ра (рим­ские цифры).

Рас­сто­я­ние между двумя точ­ка­ми A(x₁; y₁) и B(x₂; y₂) вы­чис­ля­ет­ся по фор­му­ле:

Даны два вход­ных файла (файл А и файл Б). Для файла А опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: A₁  — ми­ни­маль­ное рас­сто­я­ние от цен­тра кла­сте­ра с наи­мень­шим ко­ли­че­ством точек до крас­но­го ги­ган­та, и A₂  — мак­си­маль­ное рас­сто­я­ние от цен­тра кла­сте­ра с наи­мень­шим ко­ли­че­ством точек до крас­но­го ги­ган­та.

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

В от­ве­те за­пи­ши­те че­ты­ре числа: в пер­вой стро­ке  — целую часть про­из­ве­де­ния A₁ × 10 000, затем целую часть про­из­ве­де­ния A₂ × 10 000; во вто­рой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния B₁ × 10 000, затем целую часть про­из­ве­де­ния B₂ × 10 000.

Ответ: