На ри­сун­ке схема дорог изоб­ра­же­на в виде графа, в таб­ли­це со­дер­жат­ся све­де­ния о длине этих дорог в ки­ло­мет­рах. Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Из­вест­но, что до­ро­га CD длин­нее до­ро­ги EF. Опре­де­ли­те сумму длин дорог АB и AG.

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

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

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

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

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

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко за­глав­ные рус­ские буквы. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: А  — 000, Б  — 01, В  — 1101, Г  — 111, Д  — 0010, Е  — 100. Какое наи­мень­шее ко­ли­че­ство дво­ич­ных зна­ков по­тре­бу­ет­ся для ко­ди­ро­ва­ния слова КОКОС?

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

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

1.  Стро­ит­ся дво­ич­ная за­пись числа N без ве­ду­щих нулей.

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

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

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

1.  Дво­ич­ная за­пись числа N: 1101.

2.  В за­пи­си боль­ше еди­ниц, спра­ва при­пи­сы­ва­ет­ся еди­ни­ца: 11011.

3.  На экран вы­во­дит­ся де­ся­тич­ное зна­че­ние по­лу­чен­но­го числа 27.

Какое наи­мень­шее число, пре­вы­ша­ю­щее 100, может по­лу­чить­ся в ре­зуль­та­те ра­бо­ты ав­то­ма­та?

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

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

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

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

По­вто­ри 2 [Вперёд 15 На­пра­во 90 Вперёд 8 На­пра­во 90]

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

Гра­фи­че­ский файл с раз­ре­ше­ни­ем 1024 х 600 на жест­ком диске за­ни­ма­ет не более 120 КБайт. Опре­де­ли­те мак­си­маль­ное ко­ли­че­ство цве­тов, ко­то­рое может ис­поль­зо­вать­ся для ко­ди­ро­ва­ния дан­но­го изоб­ра­же­ния.

Ти­мо­фей со­став­ля­ет 5-⁠бук­вен­ные коды из букв Т, И, М, О, Ф, Е, Й. Буква Й может ис­поль­зо­вать­ся в коде не более од­но­го раза, при этом она не может сто­ять на пер­вом месте, на по­след­нем месте и рядом с бук­вой И. Все осталь­ные буквы могут встре­чать­ся про­из­воль­ное ко­ли­че­ство раз или не встре­чать­ся со­всем. Сколь­ко раз­лич­ных кодов может со­ста­вить Ти­мо­фей?

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

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

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

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

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

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

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

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

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

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

Цикл

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

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

КОНЕЦ ПОКА

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

Какая стро­ка по­лу­чит­ся в ре­зуль­та­те при­ме­не­ния при­ведённой ниже про­грам­мы к стро­ке, со­сто­я­щей из 82 еди­ниц?

НА­ЧА­ЛО

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

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

            ТО за­ме­нить (11111, 88)

        ИНАЧЕ

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

                ТО за­ме­нить (888, 8)

            КОНЕЦ ЕСЛИ

        КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

КОНЕЦ

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

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

Для узла с IP-⁠ад­ре­сом 117.191.88.37 адрес сети равен 117.191.80.0. Чему равен тре­тий слева байт маски? Ответ за­пи­ши­те в виде де­ся­тич­но­го числа.

Зна­че­ние вы­ра­же­ния 9¹² + 3⁸ − 3? за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 3.

Сколь­ко цифр 2 со­дер­жит­ся в этой за­пи­си?

Обо­зна­чим через m&n по­раз­ряд­ную конъ­юнк­цию не­от­ри­ца­тель­ных целых чисел m и n.

Так, на­при­мер, 12&6  =  1100₂&0110₂  =  0100₂  =  4.

Для ка­ко­го наи­боль­ше­го це­ло­го числа А фор­му­ла

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

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

F(1)  =  3;

F(2)  =  3;

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

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

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

Ответ:

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

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

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

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

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

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

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

Ответ:

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в кучу один или два камня или уве­ли­чить ко­ли­че­ство кам­ней в куче в три раза. На­при­мер, имея кучу из 15 кам­ней, за один ход можно по­лу­чить кучу из 16, 17 или 45 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 65. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 65 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 64.

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в кучу один или два камня или уве­ли­чить ко­ли­че­ство кам­ней в куче в три раза. На­при­мер, имея кучу из 15 кам­ней, за один ход можно по­лу­чить кучу из 16, 17 или 45 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 65. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 65 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 64.

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

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

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

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в кучу один или два камня или уве­ли­чить ко­ли­че­ство кам­ней в куче в три раза. На­при­мер, имея кучу из 15 кам­ней, за один ход можно по­лу­чить кучу из 16, 17 или 45 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 65. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 65 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 64.

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

Най­ди­те ми­ни­маль­ное зна­че­ние 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.  Умно­жить на 2.

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

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

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

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

При­мер. В стро­ке TTTT пара сим­во­лов встре­ча­ет­ся ровно 3 раза.

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

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

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

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

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

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

Цены то­ва­ров ука­за­ны в про­из­воль­ном по­ряд­ке.

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

В от­ве­те за­пи­ши­те два целых числа: сна­ча­ла ми­ни­маль­ную цену, ко­то­рую пла­ни­ро­вал за­пла­тить по­ку­па­тель из­на­чаль­но, если бы бес­плат­ным был 3-⁠й товар в любой по­куп­ке, со­сто­я­щей из 3 пред­ме­тов. А затем за­пи­ши­те цену, ко­то­рую он за­пла­тил.

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

Ти­по­вой при­мер вход­ных дан­ных:

4

80

30

50

40

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

Ответ:

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

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

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

Ответ: