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

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

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

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

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

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

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

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

За­го­ло­вок таб­ли­цы имеет сле­ду­ю­щий вид.

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко во­семь букв: Г, Р, У, Д, И, Н, К, А. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано.

Ко­до­вые слова для не­ко­то­рых букв из­вест­ны.

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

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

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

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

2.  Далее эта за­пись об­ра­ба­ты­ва­ет­ся по сле­ду­ю­ще­му пра­ви­лу:

а)  если число N де­лит­ся на 3, то слева к нему при­пи­сы­ва­ет­ся «1», а спра­ва «02»;

б)  если число N на 3 не де­лит­ся, то оста­ток от де­ле­ния на 3 умно­жа­ет­ся на 4, пе­ре­во­дит­ся в тро­ич­ную за­пись и до­пи­сы­ва­ет­ся в конец числа.

По­лу­чен­ная таким об­ра­зом за­пись яв­ля­ет­ся тро­ич­ной за­пи­сью ис­ко­мо­го числа R.

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

На­при­мер, для ис­ход­но­го числа 11₁₀  =  102₃ ре­зуль­та­том яв­ля­ет­ся число 10222₃  =  107₁₀, а для ис­ход­но­го числа 12₁₀  =  110₃  — это число 111002₃  =  353_10.

Ука­жи­те мак­си­маль­ное число N, после об­ра­бот­ки ко­то­ро­го с по­мо­щью этого ал­го­рит­ма по­лу­ча­ет­ся число R, не пре­вы­ша­ю­щее 350.

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

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

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

На­пра­во 180

По­вто­ри 9 [Вперёд 66 На­ле­во 90 Вперёд 100 На­ле­во 90]

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

Вперёд 27 На­ле­во 90 Вперёд 41 На­пра­во 90

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

По­вто­ри 9 [Вперёд 120 На­пра­во 90 Вперёд 99 На­пра­во 90]

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

При­бор ав­то­ма­ти­че­ской фик­са­ции на­ру­ше­ний пра­вил до­рож­но­го дви­же­ния де­ла­ет цвет­ные фо­то­гра­фии раз­ме­ром 1800 × 1200 пик­се­лей, при этом ис­поль­зу­ет­ся па­лит­ра из 2048 цве­тов. Все сним­ки груп­пи­ру­ют­ся в па­ке­ты по Х (Х  — на­ту­раль­ное число) штук и пе­ре­да­ют­ся по ка­на­лу связи. Из­вест­но, что время пе­ре­да­чи од­но­го та­ко­го па­ке­та за­ни­ма­ет ровно 2,5 часа, а про­пуск­ная спо­соб­ность ка­на­ла равна 36 693 360 бит/c. Опре­де­ли­те, чему равно зна­че­ние Х. В от­ве­те за­пи­ши­те толь­ко число.

Опре­де­ли­те ко­ли­че­ство 14-⁠рич­ных ше­сти­знач­ных чисел, в за­пи­си ко­то­рых со­дер­жит­ся не менее одной цифры 4 и ровно две цифры с чис­ло­вым зна­че­ни­ем, пре­вы­ша­ю­щим 10, причём сто­я­щие рядом.

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

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

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

—  ко­ли­че­ство чётных и нечётных чисел в стро­ке оди­на­ко­во.

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

C по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз встре­ча­ет­ся слово «их» или «Их» в тек­сте по­след­них двух глав ро­ма­на И. С. Тур­ге­не­ва «Отцы и дети». Дру­гие формы этого слова учи­ты­вать не сле­ду­ет.

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

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 20 сим­во­лов. В ка­че­стве сим­во­лов ис­поль­зу­ют про­пис­ные и строч­ные буквы ла­тин­ско­го ал­фа­ви­та, а также де­ся­тич­ные цифры и сим­во­лы из 30-⁠сим­воль­но­го спе­ци­аль­но­го ал­фа­ви­та. В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Кроме соб­ствен­но па­ро­ля, для каж­до­го поль­зо­ва­те­ля в си­сте­ме хра­нят­ся до­пол­ни­тель­ные све­де­ния, для чего вы­де­ле­но 45 байт на од­но­го поль­зо­ва­те­ля. В ком­пью­тер­ной си­сте­ме вы­де­ле­но 3 Мбай­та для хра­не­ния све­де­ний о поль­зо­ва­те­лях. О каком наи­боль­шем ко­ли­че­стве поль­зо­ва­те­лей может быть со­хра­не­на ин­фор­ма­ция в си­сте­ме? В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство поль­зо­ва­те­лей.

При­ме­ча­ние. В ла­тин­ском ал­фа­ви­те 26 букв.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ос­но­ва­ние си­сте­мы счис­ле­ния ука­зы­вать не нужно.

На чис­ло­вой пря­мой даны два от­рез­ка: M  =  [257; 382] и N  =  [361; 513]. Ука­жи­те наи­мень­шую воз­мож­ную длину та­ко­го от­рез­ка A, что ло­ги­че­ское вы­ра­же­ние

ис­тин­но (т. е. при­ни­ма­ет зна­че­ние 1) при любом зна­че­нии пе­ре­мен­ной х.

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

если

если и крат­но 7;

если и не крат­но 7.

На­зо­ви­те ми­ни­маль­ное зна­че­ние n, для ко­то­ро­го функ­ция F(n) опре­де­ле­на и

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел. Эле­мен­ты по­сле­до­ва­тель­но­сти могут при­ни­мать целые зна­че­ния от –10 000 до 10 000 вклю­чи­тель­но.

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

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

Ответ:

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

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

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

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

В от­ве­те ука­жи­те два числа  — сна­ча­ла мак­си­маль­ную сумму, затем ми­ни­маль­ную.

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

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

Ответ:

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

Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 313.

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

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

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

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

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

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

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

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

Ответ:

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

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

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

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

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

Опре­де­ли­те сумму но­ме­ров всех про­цес­сов, ко­то­рые за­пу­стят­ся, но не успе­ют за­вер­шить­ся за пер­вые T  =  30 мс с мо­мен­та за­пус­ка пер­во­го про­цес­са (при усло­вии, что все не­за­ви­си­мые друг от друга про­цес­сы могут вы­пол­нять­ся па­рал­лель­но и ни­ка­кие за­держ­ки не до­пус­ка­ют­ся).

На­при­мер, для при­ведённой таб­ли­цы, при T  =  6 мс, про­цес­сы с ID 3 и 4 будут за­пу­ще­ны через 4 мс с мо­мен­та за­пус­ка пер­во­го про­цес­са и на мо­мент вре­ме­ни T за­вер­ше­ны ещё не будут. Ответ 7.

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

A.  вычти 7

B.  по­де­ли на 2

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

Сколь­ко су­ще­ству­ет таких про­грамм, ко­то­рые ис­ход­ное число 300 пре­об­ра­зу­ют в число 40, при этом тра­ек­то­рия вы­чис­ле­ний не со­дер­жит чисел 61 и 122?

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

На­при­мер, для про­грам­мы ABA при ис­ход­ном числе 100 тра­ек­то­рия со­сто­ит из чисел 93, 47, 40.

Тек­сто­вый файл со­сто­ит не более чем из 10⁷ сим­во­лов и со­дер­жит толь­ко за­глав­ные буквы ла­тин­ско­го ал­фа­ви­та и де­ся­тич­ные цифры. Назовём «чис­лом» не­пу­стую не­пре­рыв­ную под­по­сле­до­ва­тель­ность цифр, огра­ни­чен­ную бук­ва­ми по обеим сто­ро­нам. Най­ди­те ми­ни­маль­ную длину под­стро­ки, со­дер­жа­щую не менее K  =  10 000 «чисел». В от­ве­те ука­жи­те длину най­ден­ной стро­ки.

На­при­мер, в стро­ке AC12BDE3F2ED6 всего три «числа»: 12, 3 и 2. При K  =  2 от­ве­том для дан­ной стро­ки будет яв­лять­ся число 5: это под­стро­ка E3F2E.

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

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

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

В пер­вой стро­ке ука­за­но на­ту­раль­ное число N   — ко­ли­че­ство ска­ни­ро­ва­ний за сутки.

Сле­ду­ю­щие N строк со­дер­жат пары чисел: время на­ча­ла и время окон­ча­ния каж­до­го ска­ни­ро­ва­ния (не­от­ри­ца­тель­ные числа, мень­шие 86 400 000).

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

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

5

10 100

20 120

130 170

150 200

250 400

При таких ис­ход­ных дан­ных про­ме­жут­ков хотя бы с одним ска­ни­ро­ва­ни­ем было 3: с 10 до 120 мс, с 130 до 2000 мс и с 250 до 400 мс. Их сум­мар­ная дли­тель­ность равна

Ответ для при­ме­ра: 3; 330.

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

Ответ:

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

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

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

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

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

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

Для файла А най­ди­те пары точек, ко­то­рые об­ра­зу­ют диа­метр каж­до­го кла­сте­ра. Затем вы­чис­ли­те два числа: P_x  — мак­си­маль­ную из сумм абс­цисс этих точек для всех кла­сте­ров и P_y  — мак­си­маль­ную из сумм ор­ди­нат этих точек для всех кла­сте­ров. Для файла Б най­ди­те два числа: Q₁  — диа­метр кла­сте­ра с мак­си­маль­ным ко­ли­че­ством точек и Q₂  — мак­си­маль­ное рас­сто­я­ние от точки, об­ра­зу­ю­щей диа­метр од­но­го кла­сте­ра, до точки, об­ра­зу­ю­щей диа­метр дру­го­го кла­сте­ра.

Га­ран­ти­ру­ет­ся, что во всех кла­сте­рах ко­ли­че­ство точек раз­лич­но.

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

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

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

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

Ответ: