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

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

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

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

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

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

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

Ис­поль­зуя ин­фор­ма­цию из при­ведённой базы дан­ных, опре­де­ли­те, в ма­га­зи­ны ка­ко­го рай­о­на Мо­ло­ко­за­вод №1 по­ста­вил с 4 по 6 июня то­ва­ров на наи­боль­шую сумму.

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко во­семь букв: К, Л, М, Н, О, П, Р, С. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: К  — 001, Н  — 100, Р  — 111. Какое наи­мень­шее ко­ли­че­ство дво­ич­ных зна­ков по­тре­бу­ет­ся для ко­ди­ро­ва­ния слова МО­ЛО­КО­СОС?

При­ме­ча­ние. Усло­вие Фано озна­ча­ет, что ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова.

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

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

2.  В конец за­пи­си (спра­ва) до­пи­сы­ва­ет­ся оста­ток от де­ле­ния числа N на 3.

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

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

1.  Тро­ич­ная за­пись числа N: 102.

2.  Оста­ток от де­ле­ния 11 на 3 равен 2, новая за­пись: 1022.

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

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

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

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

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

На­пра­во 180

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

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

Вперёд 18 На­ле­во 90 Вперёд 38 На­пра­во 90

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

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

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

Му­зы­каль­ный фраг­мент был за­пи­сан в фор­ма­те сте­рео (двух­ка­наль­ная за­пись), оциф­ро­ван и со­хранён в виде файла без ис­поль­зо­ва­ния сжа­тия дан­ных. Раз­мер по­лу­чен­но­го файла без учёта раз­ме­ра за­го­лов­ка файла  — 48 Мбайт. Затем тот же му­зы­каль­ный фраг­мент был за­пи­сан по­втор­но в фор­ма­те моно и оциф­ро­ван с раз­ре­ше­ни­ем в 1,5 раза выше и ча­сто­той дис­кре­ти­за­ции в 3 раза мень­ше, чем в пер­вый раз. Сжа­тие дан­ных не про­из­во­ди­лось. Ука­жи­те раз­мер в Мбайт файла, по­лу­чен­но­го при по­втор­ной за­пи­си. В от­ве­те за­пи­ши­те толь­ко целое число, еди­ни­цу из­ме­ре­ния пи­сать не нужно. Ис­ко­мый объём не учи­ты­ва­ет раз­ме­ра за­го­лов­ка файла.

Опре­де­ли­те ко­ли­че­ство пя­ти­знач­ных чисел, за­пи­сан­ных в вось­ме­рич­ной си­сте­ме счис­ле­ния, в за­пи­си ко­то­рых толь­ко одна цифра 6, при этом ни­ка­кая нечётная цифра не стоит рядом с циф­рой 6.

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

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

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

—  все числа рас­по­ло­же­ны в не­убы­ва­ю­щем по­ряд­ке.

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

С по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз встре­ча­ет­ся от­дель­ное слово «как» со строч­ной буквы в тек­сте тре­тьей части тома 2 ро­ма­на Л. Н. Тол­сто­го «Война и мир». Со­че­та­ния букв «как» в слож­ных сло­вах, со­единённых де­фи­сом, учи­ты­вать не сле­ду­ет. В от­ве­те ука­жи­те толь­ко число

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 11 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы А, Б, В, Е, Ж, М, Н, Р, У, Я (таким об­ра­зом, ис­поль­зу­ет­ся 10 раз­лич­ных сим­во­лов). Каж­дый такой па­роль в ком­пью­тер­ной си­сте­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством байт (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит). Ука­жи­те объём па­мя­ти в бай­тах, от­во­ди­мый этой си­сте­мой для за­пи­си 70 па­ро­лей.

В от­ве­те за­пи­ши­те толь­ко число, слово «байт» пи­сать не нужно.

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

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

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

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

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

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

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

НА­ЧА­ЛО

                ПОКА НЕ на­шлось (00)

                        за­ме­нить (033, 21120)

                        за­ме­нить (034, 22120)

                        за­ме­нить (04, 220)

                        за­ме­нить (030, 100)

                КОНЕЦ ПОКА

КОНЕЦ

Из­вест­но, что в ис­ход­ной стро­ке A было ровно два нуля  — на пер­вом и на по­след­нем месте, а после вы­пол­не­ния дан­ной про­грам­мы по­лу­чи­лась стро­ка B, со­дер­жа­щая 65 цифр, и сумма цифр стро­ки B ока­за­лась про­стым чис­лом. Какое наи­мень­шее ко­ли­че­ство троек могло быть в стро­ке A?

В тер­ми­но­ло­гии сетей TCP/⁠IP мас­кой сети на­зы­ва­ет­ся дво­ич­ное число, опре­де­ля­ю­щее, какая часть IP-⁠ад­ре­са узла сети от­но­сит­ся к ад­ре­су сети, а какая  — к ад­ре­су са­мо­го узла в этой сети. Обыч­но маска за­пи­сы­ва­ет­ся по тем же пра­ви­лам, что и IP-⁠адрес,  — в виде четырёх бай­тов, причём каж­дый байт за­пи­сы­ва­ет­ся в виде де­ся­тич­но­го числа. При этом в маске сна­ча­ла (в стар­ших раз­ря­дах) стоят еди­ни­цы, а затем с не­ко­то­ро­го раз­ря­да  — нули. Адрес сети по­лу­ча­ет­ся в ре­зуль­та­те при­ме­не­ния по­раз­ряд­ной конъ­юнк­ции к за­дан­ным IP-⁠ад­ре­су узла и маске.

На­при­мер, если IP-⁠адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-⁠ад­ре­сом 117.191.37.84 адрес сети равен 117.191.37.80. Чему равно наи­мень­шее воз­мож­ное зна­че­ние по­след­не­го (са­мо­го пра­во­го) байта маски? Ответ за­пи­ши­те в виде де­ся­тич­но­го числа.

Зна­че­ние ариф­ме­ти­че­ско­го вы­ра­же­ния 9⁷ + 3²¹ − 9 за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 3. Сколь­ко цифр 2 со­дер­жит­ся в этой за­пи­си?

На чис­ло­вой пря­мой даны два от­рез­ка: Р  =  [3, 38] и Q  =  [21, 57]. Ка­ко­ва наи­боль­шая воз­мож­ная длина ин­тер­ва­ла A, что ло­ги­че­ское вы­ра­же­ние

тож­де­ствен­но ис­тин­но, то есть при­ни­ма­ет зна­че­ние 1 при любом зна­че­нии пе­ре­мен­ной х.

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

F(1)  =  3;

F(n)  =  F(n – 1) · (n – 1) при n > 1.

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

В файле со­дер­жит­ся по­сле­до­ва­тель­ность из 10 000 целых по­ло­жи­тель­ных чисел. Каж­дое число не пре­вы­ша­ет 10 000. Опре­де­ли­те и за­пи­ши­те в от­ве­те сна­ча­ла ко­ли­че­ство пар эле­мен­тов по­сле­до­ва­тель­но­сти, у ко­то­рых сумма эле­мен­тов крат­на 80 и хотя бы один эле­мент из пары де­лит­ся на 50, затем мак­си­маль­ную из сумм эле­мен­тов таких пар. В дан­ной за­да­че под парой под­ра­зу­ме­ва­ет­ся два раз­лич­ных эле­мен­та по­сле­до­ва­тель­но­сти. По­ря­док эле­мен­тов в паре не важен.

Ответ:

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

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

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

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

Для ука­зан­ных вход­ных дан­ных от­ве­том долж­на быть пара чисел 41 и 22.

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

до­ба­вить в кучу один ка­мень, или

до­ба­вить в кучу три камня, или

уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза.

На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11, 13 или 20 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

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

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

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

до­ба­вить в кучу один ка­мень, или

до­ба­вить в кучу три камня, или

уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза.

На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11, 13 или 20 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

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

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

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

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

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

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

до­ба­вить в кучу один ка­мень, или

до­ба­вить в кучу три камня, или

уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза.

На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11, 13 или 20 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

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

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

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

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

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

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

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

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

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

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

2.  Умно­жить на 2.

Пер­вая ко­ман­да уве­ли­чи­ва­ет число на экра­не на 1, вто­рая умно­жа­ет его на 2.

Про­грам­ма для Вы­чис­ли­те­ля  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 1 ре­зуль­та­том яв­ля­ет­ся число 21 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 10 и не со­дер­жит числа 18?

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

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов L, D и R. Опре­де­ли­те мак­си­маль­ную длину це­поч­ки вида LDRLDRLDR... (со­став­лен­ной из фраг­мен­тов LDR, по­след­ний фраг­мент может быть не­пол­ным).

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

На­пи­ши­те про­грам­му, ко­то­рая ищет среди целых чисел, при­над­ле­жа­щих чис­ло­во­му от­рез­ку [201455; 201470], числа, име­ю­щие ровно 4 раз­лич­ных на­ту­раль­ных де­ли­те­ля. Вы­ве­ди­те эти че­ты­ре де­ли­те­ля для каж­до­го най­ден­но­го числа в по­ряд­ке воз­рас­та­ния.

Ответ:

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

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

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

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

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

Ответ:

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

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

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

Об­ра­бот­ка ре­зуль­та­тов экс­пе­ри­мен­та вклю­ча­ет сле­ду­ю­щие шаги:

1)  кла­стер, со­дер­жа­щий наи­мень­шее число точек, ис­клю­ча­ет­ся;

2)  опре­де­ля­ют­ся цен­т­ро­и­ды всех остав­ших­ся кла­сте­ров;

3)  для най­ден­ных цен­т­ро­и­дов вы­чис­ля­ет­ся сред­няя точка.

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

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

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

В от­ве­те за­пи­ши­те че­ты­ре числа: сна­ча­ла (в пер­вой стро­ке) ко­ор­ди­на­ты X и Y сред­ней точки для файла A, затем (во вто­рой стро­ке) ко­ор­ди­на­ты X и Y сред­ней точки для файла B.

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

Ответ: