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

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

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

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

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

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко че­ты­ре буквы: А, Б, В, Г; для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для букв А, Б, В ис­поль­зу­ют­ся такие ко­до­вые слова: А  — 0; Б  — 110; В  — 101.

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

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

Ав­то­мат по­лу­ча­ет на вход четырёхзнач­ное число. По этому числу стро­ит­ся новое число по сле­ду­ю­щим пра­ви­лам.

1.  Скла­ды­ва­ют­ся от­дель­но пер­вая и вто­рая цифры, вто­рая и тре­тья цифры, а также тре­тья и четвёртая цифры.

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

При­мер. Ис­ход­ное число: 9575. Суммы: 9 + 5  =  14; 5 + 7  =  12; 7 + 5  =  12. Наи­боль­шие суммы: 14, 12. Ре­зуль­тат: 1214.

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

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

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

Для хра­не­ния в ин­фор­ма­ци­он­ной си­сте­ме до­ку­мен­ты ска­ни­ру­ют­ся с раз­ре­ше­ни­ем 300 dpi и цве­то­вой си­сте­мой, со­дер­жа­щей 2²⁴  =  16 777 216 цве­тов. Ме­то­ды сжа­тия изоб­ра­же­ний не ис­поль­зу­ют­ся. Сред­ний раз­мер от­ска­ни­ро­ван­но­го до­ку­мен­та со­став­ля­ет 18 Мбайт. В целях эко­но­мии было ре­ше­но пе­рей­ти на раз­ре­ше­ние 150 dpi и цве­то­вую си­сте­му, со­дер­жа­щую 2¹⁶  =  65 536 цве­тов. Сколь­ко Мбайт будет со­став­лять сред­ний раз­мер до­ку­мен­та, от­ска­ни­ро­ван­но­го с изменёнными па­ра­мет­ра­ми?

Все 4-⁠бук­вен­ные слова, со­став­лен­ные из букв М, У, Х, А за­пи­са­ны в ал­фа­вит­ном по­ряд­ке и про­ну­ме­ро­ва­ны.

Вот на­ча­ло спис­ка:

1.  АААА

2.  АААМ

3.  АААУ

4.  АААХ

5.  ААМА

На­пи­ши­те номер слова ХУХХ.

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

Най­ди­те раз­ность между ми­ни­маль­ным зна­че­ни­ем тем­пе­ра­ту­ры и её сред­ним ариф­ме­ти­че­ским зна­че­ни­ем. Ответ округ­ли­те до це­ло­го числа.

С по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз, не счи­тая сно­сок, встре­ча­ет­ся слово «Оне­гин» в тек­сте ро­ма­на в сти­хах А. С. Пуш­ки­на «Ев­ге­ний Оне­гин». Дру­гие формы слова «Оне­гин», такие как «Оне­ги­на», «Оне­ги­ным» и т. д., учи­ты­вать не сле­ду­ет. В от­ве­те ука­жи­те толь­ко число.

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

Опре­де­ли­те, сколь­ко байт не­об­хо­ди­мо для хра­не­ния 50 па­ро­лей.

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

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

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

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

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

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

ис­пол­ни­те­ля при этом не из­ме­ня­ет­ся.

Цикл

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

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

    КОНЕЦ ПОКА

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

НА­ЧА­ЛО

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

    за­ме­нить (12, 4)

КОНЕЦ ПОКА

КОНЕЦ

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

На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, И, К. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город К?

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

На чис­ло­вой пря­мой даны два от­рез­ка: Р  =  [30, 45] и Q  =  [40, 55]. Ка­ко­ва наи­мень­шая воз­мож­ная длина ин­тер­ва­ла A, что обе при­ведённые ниже фор­му­лы ис­тин­ны при любом зна­че­нии пе­ре­мен­ной х:

По­сле­до­ва­тель­ность чисел Люка за­да­ет­ся ре­кур­рент­ным со­от­но­ше­ни­ем:

F(1)  =  2;

F(2)  =  1;

F(n)  =  F(n–2) + F(n–1) при n > 2, где n  — на­ту­раль­ное число.

Чему равно вось­мое число в по­сле­до­ва­тель­но­сти Люка? В от­ве­те за­пи­ши­те толь­ко на­ту­раль­ное число.

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

Ответ:

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

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

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це.

При­мер вход­ных дан­ных (для таб­ли­цы раз­ме­ром 4 × 4):

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 5 кам­ней, а в дру­гой  — 9 кам­ней; такую по­зи­цию мы будем обо­зна­чать (5, 9). За один ход из по­зи­ции (5, 9) можно по­лу­чить любую из четырёх по­зи­ций: (6, 9), (10, 9), (5, 10), (5, 18).

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

В на­чаль­ный мо­мент в пер­вой куче было 8 кам­ней, во вто­рой куче  — S кам­ней; 1 ≤ S ≤ 68.

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 5 кам­ней, а в дру­гой  — 9 кам­ней; такую по­зи­цию мы будем обо­зна­чать (5, 9). За один ход из по­зи­ции (5, 9) можно по­лу­чить любую из четырёх по­зи­ций: (6, 9), (10, 9), (5, 10), (5, 18).

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

В на­чаль­ный мо­мент в пер­вой куче было 8 кам­ней, во вто­рой куче  — S кам­ней; 1 ≤ S ≤ 68.

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

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

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

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 5 кам­ней, а в дру­гой  — 9 кам­ней; такую по­зи­цию мы будем обо­зна­чать (5, 9). За один ход из по­зи­ции (5, 9) можно по­лу­чить любую из четырёх по­зи­ций: (6, 9), (10, 9), (5, 10), (5, 18).

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

В на­чаль­ный мо­мент в пер­вой куче было 8 кам­ней, во вто­рой куче  — S кам­ней; 1 ≤ S ≤ 68.

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

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

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

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

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

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

Пер­вая ко­ман­да уве­ли­чи­ва­ет число на экра­не на 1, вто­рая уве­ли­чи­ва­ет его на 3. Про­грам­ма для ис­пол­ни­те­ля Май17  — это по­сле­до­ва­тель­ность ко­манд.

Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 1 ре­зуль­та­том яв­ля­ет­ся число 15 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 8? Тра­ек­то­рия вы­чис­ле­ний про­грам­мы  — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 121 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 8, 11, 12.

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов X, Y и Z. Опре­де­ли­те длину самой длин­ной по­сле­до­ва­тель­но­сти, со­сто­я­щей из сим­во­лов X. Хотя бы один сим­вол X на­хо­дит­ся в по­сле­до­ва­тель­но­сти.

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

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

На­при­мер, в диа­па­зо­не [12; 15] ровно шесть раз­лич­ных на­ту­раль­ных де­ли­те­лей имеет число 12, по­это­му для этого диа­па­зо­на вывод на экра­не дол­жен со­дер­жать сле­ду­ю­щие зна­че­ния:

1 2 3 4 6 12

Ответ:

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

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

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

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

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

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

100 4

80

30

50

40

При таких ис­ход­ных дан­ных можно со­хра­нить файлы мак­си­мум двух поль­зо­ва­те­лей. Воз­мож­ные объёмы этих двух фай­лов  — 30 и 40, 30 и 50 или 40 и 50. Наи­боль­ший объём файла из пе­ре­чис­лен­ных пар  — 50, по­это­му ответ для при­ведённого при­ме­ра:

2 50

Ответ:

На вход про­грам­мы по­сту­па­ет по­сле­до­ва­тель­ность из n целых по­ло­жи­тель­ных чисел. Рас­смат­ри­ва­ют­ся все пары эле­мен­тов по­сле­до­ва­тель­но­сти a_i и a_j, такие, что i < j и a_i > a_j (пер­вый эле­мент пары боль­ше вто­ро­го; i и j  — по­ряд­ко­вые но­ме­ра чисел в по­сле­до­ва­тель­но­сти вход­ных дан­ных). Среди пар, удо­вле­тво­ря­ю­щих этому усло­вию, не­об­хо­ди­мо найти и на­пе­ча­тать пару с мак­си­маль­ной сум­мой эле­мен­тов, ко­то­рая де­лит­ся на m  =  120. Если среди най­ден­ных пар мак­си­маль­ную сумму имеют не­сколь­ко, то можно на­пе­ча­тать любую из них.

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

В пер­вой стро­ке вход­ных дан­ных задаётся ко­ли­че­ство чисел n (2 ≤ n ≤ 12 000).

В каж­дой из по­сле­ду­ю­щих n строк за­пи­са­но одно целое по­ло­жи­тель­ное число, не пре­вы­ша­ю­щее 10 000.

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

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

6

60

140

61

100

300

59

При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных:

140 100 В от­ве­те ука­жи­те че­ты­ре числа: сна­ча­ла ис­ко­мую пару чисел для файла А (два числа через про­бел), затем для файла B (два числа через про­бел).

Ответ:

По­яс­не­ние. Из шести за­дан­ных чисел можно со­ста­вить три пары, сумма эле­мен­тов ко­то­рых де­лит­ся на m  =  120: 60 + 300, 140 + 100 и 61 + 59. Во вто­рой и тре­тьей из этих пар пер­вый эле­мент боль­ше вто­ро­го, но во вто­рой паре сумма боль­ше.