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

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

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

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

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

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

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

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

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

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

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

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

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

Все за­глав­ные буквы рус­ско­го ал­фа­ви­та за­ко­ди­ро­ва­ны не­рав­но­мер­ным дво­ич­ным кодом, в ко­то­ром ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это усло­вие обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: И  — 111, Н  — 010, Ф  — 011, О  — 11000, Р  — 0011, М  — 10, А  — 0010, Т  — 000, К  — 11001. Сколь­ко су­ще­ству­ет спо­со­бов на­зна­чить для буквы Ю код, длина ко­то­ро­го не пре­вы­ша­ет шести дво­ич­ных зна­ков?

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

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

2.  В по­лу­чен­ной за­пи­си все нули за­ме­ня­ют­ся на двой­ки, все двой­ки  — на нули. Из по­лу­чен­но­го числа уда­ля­ют­ся ве­ду­щие нули.

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

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

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

1.  Стро­им тро­ич­ную за­пись числа N: 35₁₀  =  1022₃.

2.  За­ме­ня­ем цифры и уда­ля­ем ве­ду­щие нули: 1022 → 1200.

3.  Пе­ре­во­дим в де­ся­тич­ную си­сте­му: 1200₃  =  45₁₀.

4.  Вы­чис­ля­ем мо­дуль раз­но­сти: |35 − 45|  =  10.

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

При каком наи­мень­шем N в ре­зуль­та­те ра­бо­ты ал­го­рит­ма по­лу­чит­ся R  =  1 864 648.

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

В на­чаль­ный мо­мент Че­ре­па­ха на­хо­дит­ся в на­ча­ле ко­ор­ди­нат и на­прав­ле­на вверх (вдоль по­ло­жи­тель­но­го на­прав­ле­ния оси ор­ди­нат).

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

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

По­вто­ри 3 [Вперёд 20 На­пра­во 90 Вперёд 4 На­пра­во 90]

По­вто­ри 3 [Вперёд 6 На­пра­во 90 Вперёд 13 На­пра­во 90]

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

Книгу объёмом 2 Мбайт за­пи­са­ли как аудиок­ни­гу. За­пись ве­лась в фор­ма­те сте­рео (2 ка­на­ла) с ча­сто­той 36 кГц и раз­ре­ше­ни­ем 24 бит. За одну ми­ну­ту за­пи­сы­ва­лось в сред­нем 1,5 Кбайт тек­ста. За­пи­сан­ный аудио­файл сжали и раз­де­ли­ли на 270 фраг­мен­тов со сред­ним раз­ме­ром 20 Мбайт. Опре­де­ли­те, на сколь­ко про­цен­тов умень­шил­ся раз­мер файла при сжа­тии. За­го­лов­ки и дру­гую слу­жеб­ную ин­фор­ма­цию не учи­ты­вать. В от­ве­те за­пи­ши­те число – округлённый до це­ло­го про­цент сжа­тия.

Сколь­ко су­ще­ству­ет на­ту­раль­ных чисел, не пре­вы­ша­ю­щих 738 000 000, за­пись ко­то­рых в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 14 со­дер­жит ровно 8 раз­лич­ных цифр?

В каж­дой стро­ке элек­трон­ной таб­ли­цы за­пи­са­ны во­семь на­ту­раль­ных чисел, раз­би­тых на две четвёрки. Пер­вая четвёрка за­ни­ма­ет столб­цы с 1 по 4, вто­рая  — с 5 по 8.

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

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

—  ми­ни­маль­ное число стро­ки на­хо­дит­ся в пер­вой четвёрке;

—  сред­нее ариф­ме­ти­че­ское чисел пер­вой четвёрки боль­ше сред­не­го ариф­ме­ти­че­ско­го чисел вто­рой четвёрки.

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

Пред­при­я­тие вы­пус­ка­ет пар­тии из­де­лий. Каж­дая пар­тия по­лу­ча­ет уни­каль­ный код из 17 сим­во­ла. Каж­дый сим­вол кода может быть любой строч­ной или за­глав­ной ла­тин­ской бук­вой. Все из­де­лия в пар­тии по­лу­ча­ют по­сле­до­ва­тель­ные но­ме­ра от 1 до об­ще­го числа из­де­лий в пар­тии.

За­пись о каж­дом из­де­лии за­но­сит­ся в ин­фор­ма­ци­он­ную си­сте­му. За­пись со­дер­жит код из­де­лия и не­ко­то­рую до­пол­ни­тель­ную ин­фор­ма­цию.

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

Для за­пи­си до­пол­ни­тель­ной ин­фор­ма­ции о каж­дом из­де­лии тре­бу­ет­ся 50 байт.

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

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

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

Эта ко­ман­да за­ме­ня­ет в стро­ке пер­вое слева вхож­де­ние це­поч­ки v на це­поч­ку w. На­при­мер, вы­пол­не­ние ко­ман­ды

за­ме­нить (111, 27)

пре­об­ра­зу­ет стро­ку 05111150 в стро­ку 0527150.

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

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

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

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

НА­ЧА­ЛО

    ПОКА на­шлось (111) ИЛИ на­шлось (22)

            за­ме­нить (111, 2)

            за­ме­нить (222, 1)

            за­ме­нить (221, 1)

            за­ме­нить (122, 1)

            за­ме­нить (22, 2)

    КОНЕЦ ПОКА

КОНЕЦ

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

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

Адрес сети по­лу­ча­ет­ся в ре­зуль­та­те при­ме­не­ния по­раз­ряд­ной конъ­юнк­ции к за­дан­но­му IP⁠-⁠ад­ре­су узла и маске.

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

Из­вест­но, что в дво­ич­ной за­пи­си ад­ре­са сети, к ко­то­рой при­над­ле­жит узел 169.25.132.59, со­дер­жит­ся столь­ко же еди­ниц, сколь­ко нулей в дво­ич­ной за­пи­си маски этой сети.

Сколь­ко ад­ре­сов, в дво­ич­ной за­пи­си ко­то­рых ровно 11 еди­ниц, со­дер­жит­ся в этой сети?

В си­сте­ме счис­ле­ния с ос­но­ва­ни­ем p вы­пол­ня­ет­ся ра­вен­ство y18x + wy98 = xxz4y. Бук­ва­ми x, y, z и w обо­зна­че­ны не­ко­то­рые цифры из ал­фа­ви­та си­сте­мы счис­ле­ния с ос­но­ва­ни­ем p.

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

Обо­зна­чим через m&n по­раз­ряд­ную конъ­юнк­цию не­от­ри­ца­тель­ных целых чисел m и n. На­при­мер, 14&5  =  1110₂&0101₂  =  0100₂  =  4. Для ка­ко­го наи­мень­ше­го не­от­ри­ца­тель­но­го це­ло­го числа А фор­му­ла

Обо­зна­чим через a%b оста­ток от де­ле­ния на­ту­раль­но­го числа a на на­ту­раль­ное число b, а через a//b  — целую часть от де­ле­ния a на b.

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

F(n)  =  0, если n  =  0;

F(n)  =  F(n//4) + n%4, если n > 0 и n%4 < 2;

F(n)  =  F(n//4) + n%4 − 1, если n%4 ≥ 2.

Най­ди­те ми­ни­маль­ное n, для ко­то­ро­го F(n)  =  27, а F(n + 1)  =  20.

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

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

—  в трой­ке есть четырёхзнач­ные числа;

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

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

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

Ответ:

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

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

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

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

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

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

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

Ответ:

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

На­при­мер, если в куче 12 кам­ней, то за один ход можно убрать 2, 3, 4 или 6 кам­ней, а если в куче 11 кам­ней, то игрок за один ход сна­ча­ла уби­ра­ет один ка­мень (остаётся 10), а затем уби­ра­ет 2 или 5 кам­ней.

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

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

В на­ча­ле игры в куче было S кам­ней, S > 9.

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

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

Ответ:

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

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

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

В мо­мент, когда про­цесс готов к за­пус­ку, он ста­вит­ся в оче­редь. Если не­сколь­ко про­цес­сов ока­зы­ва­ют­ся го­то­вы к за­пус­ку од­но­вре­мен­но, пер­вым ста­вит­ся в оче­редь тот про­цесс, у ко­то­ро­го мень­ше ID.

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

За какое время будут вы­пол­не­ны все про­цес­сы?

В от­ве­те на­пи­ши­те число  — тре­бу­е­мое время в мс.

Ис­пол­ни­тель пре­об­ра­зу­ет число на экра­не.

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

A.  Вычти 2

B.  Если число крат­но 3, Раз­де­ли на 3, Иначе Вычти 4

Про­грам­ма для ис­пол­ни­те­ля  — это по­сле­до­ва­тель­ность ко­манд.

Тра­ек­то­рия вы­чис­ле­ний про­грам­мы  — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы BAB при ис­ход­ном числе 99 тра­ек­то­рия будет со­сто­ять из чисел 33, 31, 27.

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

Тек­сто­вый файл со­сто­ит из цифр от 1 до 9, зна­ков опе­ра­ций «+», «–» и «*» (сло­же­ние, вы­чи­та­ние и умно­же­ние) и за­глав­ных ла­тин­ских букв A, B, C, D.

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

При­ме­ры пра­виль­ных сумм: «23», «115+6», «1980+12−123−51+3».

Назовём ре­зуль­та­том пра­виль­ной суммы число, ко­то­рое по­лу­чит­ся при вы­пол­не­нии за­пи­сан­ных в со­от­вет­ству­ю­щей стро­ке сло­же­ний. На­при­мер, ре­зуль­тат пра­виль­ной суммы «2+3»  — число 5, а ре­зуль­тат пра­виль­ной суммы «1+2−8+3»  — число −2.

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

В от­ве­те за­пи­ши­те ре­зуль­тат най­ден­ной суммы. Га­ран­ти­ру­ет­ся, что ответ не пре­вы­ша­ет 2 · 10⁹.

При про­ве­де­нии экс­пе­ри­мен­та за­ря­жен­ные ча­сти­цы по­па­да­ют на чув­стви­тель­ный экран, пред­став­ля­ю­щий из себя мат­ри­цу раз­ме­ром 100 000 на 100 000 точек. При по­па­да­нии каж­дой ча­сти­цы на экран в про­то­ко­ле фик­си­ру­ют­ся ко­ор­ди­на­ты по­па­да­ния: номер ряда (целое число от 1 до 100 000) и номер по­зи­ции в ряду (целое число от 1 до 100 000).

Точка экра­на, в ко­то­рую по­па­ла хотя бы одна ча­сти­ца, счи­та­ет­ся свет­лой, точка, в ко­то­рую ни одна ча­сти­ца не по­па­ла,  — тёмной.

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

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

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

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

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

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

Ответ:

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

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

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

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

При этом рас­сто­я­ние вы­чис­ля­ет­ся по стан­дарт­ной фор­му­ле рас­сто­я­ния между точ­ка­ми на ев­кли­до­вой плос­ко­сти.

Ра­ди­у­сом кла­сте­ра счи­та­ет­ся мак­си­маль­ное из рас­сто­я­ний от цен­тра до осталь­ных точек кла­сте­ра.

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

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

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

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

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

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

В от­ве­те за­пи­ши­те два числа: сна­ча­ла сред­ний ра­ди­ус для файла A, затем для файла B.

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

Ответ: