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

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

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

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

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

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

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

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

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко че­ты­ре буквы: Р, Е, К, А; для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для букв А, Р, Е ис­поль­зу­ют­ся такие ко­до­вые слова: А  — 111, Р  — 0, Е  — 100.

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

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

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

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

2.  Если сумма цифр де­ся­тич­ной за­пи­си за­дан­но­го числа нечётна, то в конец дво­ич­ной за­пи­си до­пи­сы­ва­ет­ся 1, если чётна  — 0.

3−4.  Пункт 2 по­вто­ря­ет­ся для вновь по­лу­чен­ных чисел ещё два раза.

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

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

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

2.  Сумма цифр числа 17 чётная, до­пи­сы­ва­ем к дво­ич­ной за­пи­си 0, по­лу­ча­ем 100010₂  =  34₁₀.

3.  Сумма цифр числа 34 нечётная, до­пи­сы­ва­ем к дво­ич­ной за­пи­си 1, по­лу­ча­ем 1000101₂  =  69₁₀.

4.  Сумма цифр числа 69 нечётная, до­пи­сы­ва­ем к дво­ич­ной за­пи­си 1, по­лу­ча­ем 10001011₂  =  139₁₀.

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

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

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

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

Книгу объёмом 1 Мбайт за­пи­са­ли как аудиок­ни­гу. За­пись ве­лась в фор­ма­те сте­рео (2 ка­на­ла) с ча­сто­той 48 кГц и раз­ре­ше­ни­ем 24 бит. За одну ми­ну­ту за­пи­сы­ва­лось в сред­нем 1,5 Кбайт тек­ста. Сжа­тие дан­ных поз­во­ли­ло со­кра­тить раз­мер по­лу­чен­но­го зву­ко­во­го файла на 84%. Для удоб­ства ис­поль­зо­ва­ния за­пись раз­де­ли­ли на фраг­мен­ты со сред­ним раз­ме­ром 15 Мбайт. Опре­де­ли­те ко­ли­че­ство по­лу­чен­ных фраг­мен­тов.

Свет­ла­на со­став­ля­ет коды из букв сво­е­го имени. Код дол­жен со­сто­ять из 8 букв, и каж­дая буква в нём долж­на встре­чать­ся столь­ко же раз, сколь­ко в имени Свет­ла­на. Кроме того, оди­на­ко­вые буквы в коде не долж­ны сто­ять рядом. Сколь­ко кодов может со­ста­вить Свет­ла­на?

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

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

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

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

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

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

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

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 20 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы А, Б, В, Г, Д. Каж­дый такой па­роль в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством байт, при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Опре­де­ли­те, сколь­ко байт не­об­хо­ди­мо для хра­не­ния 50 па­ро­лей.

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

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

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

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

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

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

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

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

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

НА­ЧА­ЛО

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

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

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

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

    КОНЕЦ ПОКА

КОНЕЦ

Опре­де­ли­те ко­ли­че­ство таких на­ту­раль­ных N из ин­тер­ва­ла [123 456 794; 678 901 234], для ко­то­рых в ре­зуль­та­те при­ме­не­ния дан­ной про­грам­мы к стро­ке, со­сто­я­щей из N еди­ниц, по­лу­чит­ся стро­ка, со­сто­я­щая толь­ко из двоек.

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

По за­дан­ным IP-⁠ад­ре­су узла и маске опре­де­ли­те адрес сети.

IP-⁠адрес узла: 237.195.158.37

Маска: 255.255.192.0

При за­пи­си от­ве­та вы­бе­ри­те из при­ведённых в таб­ли­це чисел че­ты­ре эле­мен­та IP-⁠ад­ре­са и за­пи­ши­те в нуж­ном по­ряд­ке со­от­вет­ству­ю­щие им буквы без ис­поль­зо­ва­ния точек.

При­мер.

Пусть ис­ко­мый адрес сети 192.168.128.0 и дана таб­ли­ца:

В этом слу­чае пра­виль­ный ответ будет HBAF.

Сколь­ко еди­ниц со­дер­жит­ся в дво­ич­ной за­пи­си зна­че­ния вы­ра­же­ния: 4¹⁶ + 2³⁶ − 8?

На чис­ло­вой пря­мой даны два от­рез­ка: P  =  [19; 84] и Q  =  [4; 51]. Ука­жи­те наи­мень­шую воз­мож­ную длину та­ко­го от­рез­ка A, для ко­то­ро­го фор­му­ла

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

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

F(1)  =  1;

F(2)  =  2;

F(n)  =  (F(n–1) − F(n–2)) * n при n > 2.

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

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

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

Ответ:

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

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

Ответ:

Для игры, опи­сан­ной в за­да­нии 19, най­ди­те ми­ни­маль­ное зна­че­ние 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

3.  Найти целую часть от де­ле­ния на 2

Вы­пол­няя первую из них, ис­пол­ни­тель умень­ша­ет число на экра­не на 1, вы­пол­няя вто­рую  — умень­ша­ет на 3, вы­пол­няя тре­тью  — делит на 2 на­це­ло, от­бра­сы­вая оста­ток. Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 31 ре­зуль­та­том яв­ля­ет­ся число 3, и при этом тра­ек­то­рия вы­чис­ле­ний не со­дер­жит чисел 20 и 8 од­но­вре­мен­но?

Тек­сто­вый файл со­сто­ит из цифр 0, 6, 7, 8, 9 и зна­ков ариф­ме­ти­че­ских опе­ра­ций «−» и «*» (вы­чи­та­ние и умно­же­ние). Опре­де­ли­те мак­си­маль­ное ко­ли­че­ство сим­во­лов в не­пре­рыв­ной по­сле­до­ва­тель­но­сти, ко­то­рая яв­ля­ет­ся кор­рект­ным ариф­ме­ти­че­ским вы­ра­же­ни­ем с це­лы­ми не­от­ри­ца­тель­ны­ми чис­ла­ми. В этом вы­ра­же­нии ни­ка­кие два знака ариф­ме­ти­че­ских опе­ра­ций не стоят рядом, в за­пи­си чисел от­сут­ству­ют не­зна­ча­щие (ве­ду­щие) нули и число 0 не имеет знака.

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

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

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

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

Ответ: