На ри­сун­ке схема дорог N-⁠ского рай­о­на изоб­ра­же­на в виде графа, в таб­ли­це со­дер­жат­ся све­де­ния о про­тяжённо­сти каж­дой из этих дорог (в ки­ло­мет­рах). Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, то ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Опре­де­ли­те, ка­ко­ва сумма про­тяжённо­стей дорог из пунк­та Б в пункт Д и из пунк­та В в пункт Е. В от­ве­те за­пи­ши­те целое число.

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

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

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

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

Даны фраг­мен­ты двух таб­лиц из базы дан­ных. Каж­дая стро­ка таб­ли­цы 2 со­дер­жит ин­фор­ма­цию о ребёнке и об одном из его ро­ди­те­лей. Ин­фор­ма­ция пред­став­ле­на зна­че­ни­ем поля ID в со­от­вет­ству­ю­щей стро­ке таб­ли­цы 1. Опре­де­ли­те на ос­но­ва­нии при­ведённых дан­ных ID де­душ­ки Ага­нян Б. Г.

При­ме­ча­ние. Де­душ­ка  — это отец од­но­го из ро­ди­те­лей.

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

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

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

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

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

2.  К этой за­пи­си до­пи­сы­ва­ют­ся спра­ва ещё два раз­ря­да по сле­ду­ю­ще­му пра­ви­лу:

а)  скла­ды­ва­ют­ся все цифры дво­ич­ной за­пи­си числа N, и оста­ток от де­ле­ния суммы на 2 до­пи­сы­ва­ет­ся в конец числа (спра­ва). На­при­мер, за­пись 11100 пре­об­ра­зу­ет­ся в за­пись 111001;

б)  над этой за­пи­сью про­из­во­дят­ся те же дей­ствия  — спра­ва до­пи­сы­ва­ет­ся оста­ток от де­ле­ния суммы её цифр на 2.

По­лу­чен­ная таким об­ра­зом за­пись (в ней на два раз­ря­да боль­ше, чем в за­пи­си ис­ход­но­го числа N) яв­ля­ет­ся дво­ич­ной за­пи­сью ис­ко­мо­го числа R. Ука­жи­те ми­ни­маль­ное число R, ко­то­рое пре­вы­ша­ет число 396 и может яв­лять­ся ре­зуль­та­том ра­бо­ты дан­но­го ал­го­рит­ма. В от­ве­те это число за­пи­ши­те в де­ся­тич­ной си­сте­ме счис­ле­ния.

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

Для хра­не­ния про­из­воль­но­го раст­ро­во­го изоб­ра­же­ния раз­ме­ром 1536 × 2048 пик­се­лей от­ве­де­но не более 6 Мбайт па­мя­ти без учёта раз­ме­ра за­го­лов­ка файла. Для ко­ди­ро­ва­ния цвета каж­до­го пик­се­ля ис­поль­зу­ет­ся оди­на­ко­вое ко­ли­че­ство бит, коды пик­се­лей за­пи­сы­ва­ют­ся в файл один за дру­гим без про­ме­жут­ков. Какое мак­си­маль­ное ко­ли­че­ство цве­тов можно ис­поль­зо­вать в изоб­ра­же­нии?

Вася со­став­ля­ет 6-⁠бук­вен­ные слова, в ко­то­рых могут быть ис­поль­зо­ва­ны толь­ко буквы В, И, Ш, Н, Я, причём буква В ис­поль­зу­ет­ся не более од­но­го раза. Каж­дая из дру­гих до­пу­сти­мых букв может встре­чать­ся в слове любое ко­ли­че­ство раз или не встре­чать­ся со­всем. Слово не долж­но на­чи­нать­ся с буквы Ш и окан­чи­вать­ся глас­ны­ми бук­ва­ми. Сло­вом счи­та­ет­ся любая до­пу­сти­мая по­сле­до­ва­тель­ность букв, не обя­за­тель­но осмыс­лен­ная. Сколь­ко су­ще­ству­ет таких слов, ко­то­рые может на­пи­сать Вася?

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

В от­ве­те за­пи­ши­те толь­ко целую часть по­лу­чив­ше­го­ся числа.

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

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

Опре­де­ли­те объём па­мя­ти (в Кбайт), не­об­хо­ди­мый для хра­не­ния 3200 иден­ти­фи­ка­то­ров. В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство Кбайт.

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

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

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

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

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

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

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

Цикл

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

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

    КОНЕЦ ПОКА

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

НА­ЧА­ЛО

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

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

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

            ИНАЧЕ за­ме­нить (88888, 888)

        КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

КОНЕЦ

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

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

Зна­че­ние ариф­ме­ти­че­ско­го вы­ра­же­ния

за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 8. Сколь­ко цифр 0 со­дер­жит­ся в этой за­пи­си?

На чис­ло­вой пря­мой даны два от­рез­ка: P  =  [17, 54] и Q  =  [37, 83]. Ка­ко­ва наи­мень­шая воз­мож­ная длина ин­тер­ва­ла A, что фор­му­ла

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

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

F(1)  =  1;

F(n)  =  n + F(n − 1), если n чётно;

F(n)  =  2 · F(n − 2), если n > 1 и при этом нечётно.

Чему равно зна­че­ние функ­ции F(24)?

Рас­смат­ри­ва­ет­ся мно­же­ство целых чисел, при­над­ле­жа­щих чис­ло­во­му от­рез­ку [16 015; 48 989], ко­то­рые де­лят­ся на 7 или 11 и не де­лят­ся на 9, 12, 13. Най­ди­те ко­ли­че­ство таких чисел и ми­ни­маль­ное из них. В от­ве­те за­пи­ши­те два целых числа: сна­ча­ла ко­ли­че­ство, затем ми­ни­маль­ное число.

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

Квад­рат раз­ли­но­ван на 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ниже на четырёх язы­ках про­грам­ми­ро­ва­ния за­пи­сан ал­го­ритм. По­лу­чив на вход число x, этот ал­го­ритм пе­ча­та­ет два числа: L и M. Ука­жи­те наи­мень­шее число x, при вводе ко­то­ро­го ал­го­ритм пе­ча­та­ет сна­ча­ла 5, а потом 8.

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

1. Вы­честь 2.

2. Вы­честь 5.

Пер­вая ко­ман­да умень­ша­ет число на экра­не на 2, вто­рая умень­ша­ет это число на 5. Про­грам­ма для ис­пол­ни­те­ля Минус  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые число 23 пре­об­ра­зу­ют в число 2?

Тек­сто­вый файл со­сто­ит не более чем из 1 200 000 сим­во­лов X, Y, и Z. Опре­де­ли­те мак­си­маль­ное ко­ли­че­ство иду­щих под­ряд сим­во­лов, среди ко­то­рых нет под­стро­ки XZZY. Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му. Ниже при­ведён файл, ко­то­рый не­об­хо­ди­мо об­ра­бо­тать с по­мо­щью дан­но­го ал­го­рит­ма.

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

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

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

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

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

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

100 4

80

30

50

40

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

Ответ:

Име­ет­ся набор дан­ных, со­сто­я­щий из троек по­ло­жи­тель­ных целых чисел. Не­об­хо­ди­мо вы­брать из каж­дой трой­ки ровно одно число так, чтобы сумма всех вы­бран­ных чисел не де­ли­лась на k  =  109 и при этом была мак­си­маль­но воз­мож­ной. Га­ран­ти­ру­ет­ся, что ис­ко­мую сумму по­лу­чить можно. Про­грам­ма долж­на на­пе­ча­тать одно число  — мак­си­маль­но воз­мож­ную сумму, со­от­вет­ству­ю­щую усло­ви­ям за­да­чи.

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых со­дер­жит в пер­вой стро­ке ко­ли­че­ство троек N (1 ≤ N ≤ 1 000 000). Каж­дая из сле­ду­ю­щих N строк со­дер­жит три на­ту­раль­ных числа, не пре­вы­ша­ю­щих 20 000.

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

6

1 3 7

5 12 6

6 9 11

5 4 8

3 5 4

1 1 1

Для ука­зан­ных вход­ных дан­ных, в слу­чае, если k  =  5, зна­че­ни­ем ис­ко­мой суммы яв­ля­ет­ся число 44.

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла А, затем для файла B.

Ответ: