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

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

Ло­ги­че­ская функ­ция F задаётся вы­ра­же­ни­ем ((y → z) ∨ (¬x ∧ w)) ≡ (w ≡ z).

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

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

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

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

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

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

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

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

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

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

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

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко семь букв: А, Б, И, К, Л, С, Ц. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: Б  — 00, К  — 010, Л  — 111. Какое наи­мень­шее ко­ли­че­ство дво­ич­ных зна­ков по­тре­бу­ет­ся для ко­ди­ро­ва­ния слова АБС­ЦИС­СА?

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

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

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

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

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

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

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

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

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

На­пра­во 90 По­вто­ри 4 [Вперёд На­пра­во 150 Вперёд На­пра­во 300].

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

В ин­фор­ма­ци­он­ной си­сте­ме хра­нят­ся изоб­ра­же­ния раз­ме­ром 1024 × 768 пик­се­лей. Ме­то­ды сжа­тия изоб­ра­же­ний не ис­поль­зу­ют­ся. Каж­дое изоб­ра­же­ние до­пол­ня­ет­ся слу­жеб­ной ин­фор­ма­ци­ей, ко­то­рая за­ни­ма­ет 1280 Кбайт. Для хра­не­ния 2048 изоб­ра­же­ний по­тре­бо­ва­лось 4 Гбайт. Сколь­ко цве­тов ис­поль­зо­ва­но в па­лит­ре каж­до­го изоб­ра­же­ния?

Борис со­став­ля­ет 6-⁠бук­вен­ные коды из букв Б, О, Р, И, С. Буквы Б и Р нужно обя­за­тель­но ис­поль­зо­вать ровно по од­но­му разу, букву С можно ис­поль­зо­вать один раз или не ис­поль­зо­вать со­всем, буквы О и И можно ис­поль­зо­вать про­из­воль­ное ко­ли­че­ство раз или не ис­поль­зо­вать со­всем. Сколь­ко раз­лич­ных кодов может со­ста­вить Борис?

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

—  в стро­ке есть толь­ко два рав­ных числа, осталь­ные 4 раз­лич­ны;

—  сред­нее ариф­ме­ти­че­ское по­вто­ря­ю­щих­ся чисел мень­ше, чем сред­нее ариф­ме­ти­че­ское осталь­ных чисел стро­ки.

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

По­весть бра­тьев Стру­гац­ких «По­не­дель­ник на­чи­на­ет­ся в суб­бо­ту» со­сто­ит из трёх ис­то­рий. Опре­де­ли­те, сколь­ко раз во вто­рой ис­то­рии, вклю­чая за­го­лов­ки, эпи­гра­фы и снос­ки, встре­ча­ют­ся слова, на­чи­на­ю­щи­е­ся c буквы Я (за­глав­ной или строч­ной) и со­дер­жа­щие не менее трёх букв. В этом за­да­нии части слова, раз­делённые де­фи­сом, рас­смат­ри­ва­ют­ся как от­дель­ные слова. На­при­мер, слово «кто-то» учи­ты­ва­ет­ся как два от­дель­ных слова: трёхбук­вен­ное и двух­бук­вен­ное.

Каж­дый со­труд­ник пред­при­я­тия по­лу­ча­ет элек­трон­ный про­пуск, на ко­то­ром за­пи­са­ны лич­ный код со­труд­ни­ка, номер под­раз­де­ле­ния и не­ко­то­рая до­пол­ни­тель­ная ин­фор­ма­ция. Лич­ный код со­сто­ит из 13 сим­во­лов, каж­дый из ко­то­рых может быть рус­ской бук­вой (ис­поль­зу­ет­ся 30 раз­лич­ных букв, каж­дая буква может быть за­глав­ной или строч­ной) или одной из цифр от 1 до 9 (ноль для за­пи­си кодов не ис­поль­зу­ет­ся). Для за­пи­си кода на про­пус­ке от­ве­де­но ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Номер под­раз­де­ле­ния  — целое число от 1 до 500, он за­пи­сан на про­пус­ке как дво­ич­ное число и за­ни­ма­ет ми­ни­маль­но воз­мож­ное целое число байт. Всего на про­пус­ке хра­нит­ся 40 байт дан­ных. Сколь­ко байт вы­де­ле­но для хра­не­ния до­пол­ни­тель­ных све­де­ний об одном со­труд­ни­ке? В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство байт.

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

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

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

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

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

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

Цикл

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

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

КОНЕЦ ПОКА

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

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

НА­ЧА­ЛО

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

        за­ме­нить (1111, 22)

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

    КОНЕЦ ПОКА

КОНЕЦ

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

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

Зна­че­ние вы­ра­же­ния 36⁷ + 6¹⁹ − 18 за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 6.

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

Для ка­ко­го наи­мень­ше­го це­ло­го не­от­ри­ца­тель­но­го числа A вы­ра­же­ние

тож­де­ствен­но ис­тин­но при любых целых не­от­ри­ца­тель­ных x и y?

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

F(1)  =  1;

F(n)  =  F(n–1) · n при n > 1.

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

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел. Эле­мен­ты по­сле­до­ва­тель­но­сти могут при­ни­мать целые зна­че­ния от −10 000 до 10 000 вклю­чи­тель­но. Опре­де­ли­те и за­пи­ши­те в от­ве­те сна­ча­ла ко­ли­че­ство пар эле­мен­тов по­сле­до­ва­тель­но­сти, в ко­то­рых хотя бы одно число де­лит­ся на 3, затем мак­си­маль­ную из сумм эле­мен­тов таких пар. В дан­ной за­да­че под парой под­ра­зу­ме­ва­ет­ся два иду­щих под­ряд эле­мен­та по­сле­до­ва­тель­но­сти. На­при­мер, для по­сле­до­ва­тель­но­сти из пяти эле­мен­тов: 6; 2; 9; –3; 6  — ответ 4 11.

Ответ:

Дана по­сле­до­ва­тель­ность ве­ще­ствен­ных чисел. Из неё не­об­хо­ди­мо вы­брать не­сколь­ко под­ряд иду­щих чисел так, чтобы каж­дое сле­ду­ю­щее число от­ли­ча­лось от преды­ду­ще­го не более чем на 10. Какую мак­си­маль­ную сумму могут иметь вы­бран­ные числа?

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

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

Для ука­зан­ных вход­ных дан­ных от­ве­том будет число 18.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.  Умно­жить на 3.

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

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

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

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

Тек­сто­вый файл со­дер­жит толь­ко за­глав­ные буквы ла­тин­ско­го ал­фа­ви­та (ABC…Z). Опре­де­ли­те сим­вол, ко­то­рый чаще всего встре­ча­ет­ся в файле сразу после буквы A.

На­при­мер, в тек­сте ABCAABADDD после буквы A два раза стоит B, по од­но­му разу  — A и D. Для этого тек­ста от­ве­том будет B.

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

Для пе­ре­воз­ки пар­тии гру­зов раз­лич­ной массы вы­де­лен гру­зо­вик, но его гру­зо­подъёмность огра­ни­че­на, по­это­му пе­ре­вез­ти сразу все грузы не удаст­ся. Грузы мас­сой от 200 до 210 кг гру­зят в первую оче­редь, га­ран­ти­ру­ет­ся, что все такие грузы по­ме­стят­ся. На остав­ше­е­ся после этого место ста­ра­ют­ся взять как можно боль­ше гру­зов. Если это можно сде­лать не­сколь­ки­ми спо­со­ба­ми, вы­би­ра­ют тот спо­соб, при ко­то­ром самый боль­шой из вы­бран­ных гру­зов имеет наи­боль­шую массу. Если и при этом усло­вии воз­мож­но не­сколь­ко ва­ри­ан­тов, вы­би­ра­ет­ся тот, при ко­то­ром наи­боль­шую массу имеет вто­рой по ве­ли­чи­не груз, и так далее. Из­вест­ны ко­ли­че­ство гру­зов, масса каж­до­го из них и гру­зо­подъёмность гру­зо­ви­ка. Не­об­хо­ди­мо опре­де­лить ко­ли­че­ство и общую массу гру­зов, ко­то­рые будут вы­ве­зе­ны при по­груз­ке по вы­ше­опи­сан­ным пра­ви­лам.

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

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

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

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

6 605

140

205

120

160

100

340 В дан­ном слу­чае сна­ча­ла нужно взять груз мас­сой 205 кг. После этого можно вы­вез­ти ещё мак­си­мум 3 груза. Это можно сде­лать тремя спо­со­ба­ми: 140 + 120 + 100, 140 + 160 + 100, 120 + 160 + 100. Вы­би­ра­ем спо­соб, при ко­то­ром вы­во­зит­ся груз наи­боль­шей воз­мож­ной массы. Таких спо­со­бов два: 140 + 160 + 100 и 120 + 160 + 100. Из этих спо­со­бов вы­би­ра­ем тот, при ко­то­ром боль­ше масса вто­ро­го по ве­ли­чи­не груза, то есть 140 + 160 + 100. Всего по­лу­ча­ет­ся 4 груза общей мас­сой 605 кг. В от­ве­те надо за­пи­сать числа 4 и 605.

Ответ:

Име­ет­ся набор дан­ных, со­сто­я­щий из троек по­ло­жи­тель­ных целых чисел. Не­об­хо­ди­мо вы­брать из каж­дой трой­ки ровно одно число так, чтобы сумма всех вы­бран­ных чисел не де­ли­лась на 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.

Ответ: