На ри­сун­ке изоб­ра­же­на схема дорог N⁠-ского рай­о­на. В таб­ли­це звёздоч­кой обо­зна­че­но на­ли­чие до­ро­ги из од­но­го населённого пунк­та в дру­гой. От­сут­ствие звёздоч­ки озна­ча­ет, что такой до­ро­ги нет.

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

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

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

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

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

При­мер. Функ­ция F за­да­на вы­ра­же­ни­ем ¬x ∨ y, за­ви­ся­щим от двух пе­ре­мен­ных, а фраг­мент таб­ли­цы имеет сле­ду­ю­щий вид.

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

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

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

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

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

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

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

На­гор­но­го рай­о­на, за пе­ри­од с 1 по 15 ок­тяб­ря вклю­чи­тель­но.

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко во­семь букв: А, Б, В, Г, Д, Е, Ж и З. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: А  — 00, Б  — 1000, В  — 010, Г  — 1001, Д  —011, Е  — 111. Какое наи­мень­шее ко­ли­че­ство дво­ич­ных зна­ков тре­бу­ет­ся для ко­ди­ро­ва­ния двух остав­ших­ся букв? В от­ве­те за­пи­ши­те сум­мар­ную длину ко­до­вых слов для букв Ж, З.

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

Это обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний.

На вход ал­го­рит­ма подаётся на­ту­раль­ное число 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  — целое число).

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

На­пра­во 90 По­вто­ри 7 [На­пра­во 45 Вперёд 11 На­пра­во 45].

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

Ви­та­лий де­ла­ет сним­ки ин­те­рес­ных мест и со­бы­тий циф­ро­вой ка­ме­рой сво­е­го смарт­фо­на. Каж­дая фо­то­гра­фия

пред­став­ля­ет собой раст­ро­вое изоб­ра­же­ние раз­ме­ром 1024 × 768 пик­се­лей и с па­лит­рой из 2²³ цве­тов. В конце дня Ви­та­лий от­прав­ля­ет сним­ки дру­зьям с по­мо­щью при­ло­же­ния-мес­сен­дже­ра. Для эко­но­мии тра­фи­ка при­ло­же­ние сжи­ма­ет сним­ки, ис­поль­зуя раз­мер 800 × 600 пик­се­лей и глу­би­ну цвета 22 бита. Сколь­ко Кбайт тра­фи­ка эко­но­мит­ся таким об­ра­зом при пе­ре­да­че 100 фо­то­гра­фий?

В от­ве­те ука­жи­те целую часть по­лу­чен­но­го числа.

Сколь­ко су­ще­ству­ет де­ся­тич­ных четырёхзнач­ных чисел, в ко­то­рых все цифры раз­лич­ны и ни­ка­кие две чётные или две нечётные цифры не стоят рядом?

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

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

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

—  сумма двух наи­боль­ших чисел стро­ки не боль­ше суммы трёх её остав­ших­ся чисел.

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

C по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз встре­ча­ет­ся слово «Ро­ма­шов» с про­пис­ной буквы в тек­сте главы V по­ве­сти А. И. Куп­ри­на «По­еди­нок». Дру­гие формы слова «Ро­ма­шов», такие как «Ро­ма­шо­ву» и т. д., учи­ты­вать не сле­ду­ет. В от­ве­те ука­жи­те толь­ко число.

На пред­при­я­тии каж­дой из­го­тов­лен­ной де­та­ли при­сва­и­ва­ют се­рий­ный номер, со­сто­я­щий из 246 сим­во­лов. В базе дан­ных для хра­не­ния каж­до­го се­рий­но­го но­ме­ра от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное число байт. При этом ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние се­рий­ных но­ме­ров, все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным чис­лом бит. Из­вест­но, что для хра­не­ния 703 569 се­рий­ных но­ме­ров до­ступ­но не более 77 Мбайт па­мя­ти. Опре­де­ли­те мак­си­маль­но воз­мож­ную мощ­ность ал­фа­ви­та, ис­поль­зу­е­мо­го для за­пи­си се­рий­ных но­ме­ров. В от­ве­те за­пи­ши­те толь­ко целое число.

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

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

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

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

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

 Цикл

    ПОКА усло­вие

        по­сле­до­ва­тель­ность ко­манд

    КОНЕЦ ПОКА

 вы­пол­ня­ет­ся, пока усло­вие ис­тин­но.

 В кон­струк­ции

    ЕСЛИ усло­вие

        ТО ко­ман­да1

        ИНАЧЕ ко­ман­да2

    КОНЕЦ ЕСЛИ

 вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но) или ко­ман­да2 (если усло­вие ложно).

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

НА­ЧА­ЛО

ПОКА на­шлось (19) ИЛИ на­шлось (399) ИЛИ на­шлось (999)

    ЕСЛИ на­шлось (19)

        ТО за­ме­нить (19, 9)

    КОНЕЦ ЕСЛИ

    ЕСЛИ на­шлось (399)

        ТО за­ме­нить (399, 91)

    КОНЕЦ ЕСЛИ

    ЕСЛИ на­шлось (999)

        ТО за­ме­нить (999, 3)

    КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

На вход при­ведённой выше про­грам­ме по­сту­па­ет стро­ка, на­чи­на­ю­ща­я­ся с цифры «1», а затем со­дер­жа­щая n цифр «9» (3 < n < 10 000).

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

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

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

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

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

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

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

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

Зна­че­ние ариф­ме­ти­че­ско­го вы­ра­же­ния 7³⁵⁰ + 7¹⁵⁰ – x, где x – целое по­ло­жи­тель­ное число, не пре­вы­ша­ю­щее 2300, за­пи­са­ли в се­ме­рич­ной си­сте­ме счис­ле­ния. Опре­де­ли­те наи­боль­шее зна­че­ние x, при ко­то­ром в се­ме­рич­ной за­пи­си числа, яв­ля­ю­ще­го­ся зна­че­ни­ем дан­но­го ариф­ме­ти­че­ско­го вы­ра­же­ния, со­дер­жит­ся ровно 200 нулей.

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

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

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

F(n)  =  n, если n ≥ 2025;

F(n)  =  n × 2 + F(n + 2), если n < 2025.

Чему равно зна­че­ние вы­ра­же­ния F(82) − F(81)?

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел. Её эле­мен­ты могут при­ни­мать целые зна­че­ния от −100 000 до 100 000

вклю­чи­тель­но.

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

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

Ответ:

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

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

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

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

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

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

усло­вия:

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

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

Если най­де­но не­сколь­ко зна­че­ний S, в от­ве­те за­пи­ши­те наи­мень­шее из них.

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

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

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

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

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

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

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

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

B. При­ба­вить 2

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

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

Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 3 ре­зуль­та­том яв­ля­ет­ся число 18, при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 14 и не со­дер­жит 8?

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

На­при­мер, для про­грам­мы CBA при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 14, 16, 17.

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

Опре­де­ли­те в этом файле по­сле­до­ва­тель­ность иду­щих под­ряд сим­во­лов, пред­став­ля­ю­щих собой за­пись мак­си­маль­но­го чётного 14-рич­но­го числа. В от­ве­те за­пи­ши­те ко­ли­че­ство сим­во­лов (зна­ча­щих цифр в за­пи­си числа) в этой по­сле­до­ва­тель­но­сти.

При­ме­ча­ние. Ла­тин­ские буквы A, B, C и D озна­ча­ют цифры из ал­фа­ви­та 14⁠-⁠рич­ной си­сте­мы счис­ле­ния.

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

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

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

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

При­мер вход­но­го файла:

5

43

40

32

40

30

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

При таких ис­ход­ных дан­ных усло­вию за­да­чи удо­вле­тво­ря­ют на­бо­ры ко­ро­бок с дли­на­ми сто­рон 30, 40 и 43 или 32, 40 и 43 со­от­вет­ствен­но, то есть ко­ли­че­ство ко­ро­бок равно 3, а длина сто­ро­ны самой ма­лень­кой ко­роб­ки равна 32.

Ответ:

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

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

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

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

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

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

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

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

Ответ: