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

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

ВНИ­МА­НИЕ! Длины от­рез­ков на схеме не от­ра­жа­ют длины дорог.

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

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

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

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

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

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

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

Таб­ли­ца «На­ли­чие» со­дер­жит за­пи­си о по­сту­пив­ших ди­ле­ру и про­дан­ных по­ку­па­те­лям ма­ши­нах. Поле Тип опе­ра­ции со­дер­жит зна­че­ние «По­сту­пи­ло ди­ле­ру» или «От­да­но по­ку­па­те­лю». За­го­ло­вок таб­ли­цы имеет вид:

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

Таб­ли­ца «Ди­ле­ры» со­дер­жит ин­фор­ма­цию о ме­стах рас­по­ло­же­ния ди­лер­ских цен­тров.

За­го­ло­вок таб­ли­цы имеет вид:

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

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

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

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

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

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

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

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

При­мер. Ис­ход­ное число: 63 179. Суммы: 6 + 1 + 9  =  16; 3 + 7  =  10. Ре­зуль­тат: 1016.

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

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

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

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

На­пра­во 60 По­вто­ри 2 [Вперёд 10 На­пра­во 120 Вперёд 5 На­пра­во 240] На­пра­во 120 Вперёд 3 На­пра­во 90 Вперёд На­пра­во 90 Вперёд 8 На­пра­во 120 По­вто­ри 2 [Вперёд 10 На­ле­во 120 Вперёд 5 На­ле­во 240].

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

Для про­ве­де­ния экс­пе­ри­мен­та за­пи­сы­ва­ет­ся зву­ко­вой фраг­мент в фор­ма­те квад­ро (четырёхка­наль­ная за­пись) с ча­сто­той дис­кре­ти­за­ции 32 кГц и 32-⁠бит­ным раз­ре­ше­ни­ем. Ре­зуль­та­ты за­пи­сы­ва­ют­ся в файл, сжа­тие дан­ных не про­из­во­дит­ся; до­пол­ни­тель­но в файл за­пи­сы­ва­ет­ся слу­жеб­ная ин­фор­ма­ция, не­об­хо­ди­мая для экс­пе­ри­мен­та, раз­мер по­лу­чен­но­го файла 97 Мбайт. Затем про­из­во­дит­ся по­втор­ная за­пись этого же фраг­мен­та в фор­ма­те моно (од­но­ка­наль­ная за­пись) с ча­сто­той дис­кре­ти­за­ции 16 кГц и 16-⁠бит­ным раз­ре­ше­ни­ем. Ре­зуль­та­ты тоже за­пи­сы­ва­ют­ся в файл без сжа­тия и со слу­жеб­ной ин­фор­ма­ци­ей, раз­мер по­лу­чен­но­го файла 7 Мбайт. Объём слу­жеб­ной ин­фор­ма­ции в обоих слу­ча­ях оди­на­ков. Ука­жи­те этот объём в ме­га­бай­тах. В от­ве­те ука­жи­те толь­ко число (ко­ли­че­ство Мбайт), еди­ни­цу из­ме­ре­ния ука­зы­вать не надо.

Ольга со­став­ля­ет 5-⁠бук­вен­ные коды из букв О, Л, Ь, Г, А. Каж­дую букву нужно ис­поль­зо­вать ровно 1 раз, при этом Ь нель­зя ста­вить пер­вым и нель­зя ста­вить после глас­ной. Сколь­ко раз­лич­ных кодов может со­ста­вить Ольга?

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

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

—  наи­боль­шее из 4 чисел мень­ше суммы трёх дру­гих;

—  все че­ты­ре числа раз­лич­ны.

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

Каж­дый со­труд­ник пред­при­я­тия по­лу­ча­ет элек­трон­ный про­пуск, на ко­то­ром за­пи­са­ны лич­ный код со­труд­ни­ка, код под­раз­де­ле­ния и не­ко­то­рая до­пол­ни­тель­ная ин­фор­ма­ция. Лич­ный код со­сто­ит из 18 букв. Для фор­ми­ро­ва­ния кодов ис­поль­зу­ет­ся 15 раз­лич­ных букв, каж­дая из ко­то­рых может быть за­глав­ной или строч­ной. Для за­пи­си кода на про­пус­ке от­ве­де­но ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Код под­раз­де­ле­ния  — целое трёхзнач­ное число, он за­пи­сан на про­пус­ке как дво­ич­ное число и за­ни­ма­ет ми­ни­маль­но воз­мож­ное целое число байт. Всего на про­пус­ке хра­нит­ся 30 байт дан­ных. Сколь­ко байт вы­де­ле­но для хра­не­ния до­пол­ни­тель­ных све­де­ний об одном со­труд­ни­ке? В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство байт.

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

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

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

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

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

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

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

Цикл

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

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

    КОНЕЦ ПОКА

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

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

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

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

    КОНЕЦ ЕСЛИ

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

На вход при­ведённой ниже про­грам­ме по­сту­па­ет стро­ка, на­чи­на­ю­ща­я­ся с сим­во­ла «>», а затем со­дер­жа­щая 10 цифр 1, 20 цифр 2 и 30 цифр 3, рас­по­ло­жен­ных в про­из­воль­ном по­ряд­ке.

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

Так, на­при­мер, если ре­зуль­тат ра­бо­ты про­грам­мы пред­став­лял бы собой стро­ку, со­сто­я­щую из 50 цифр 4, то вер­ным от­ве­том было бы число 200.

НА­ЧА­ЛО

ПОКА на­шлось (>1) ИЛИ на­шлось (>2) ИЛИ на­шлось (>3)

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

        ТО за­ме­нить (>1, 22>)

    КОНЕЦ ЕСЛИ

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

        ТО за­ме­нить (>2, 2>)

    КОНЕЦ ЕСЛИ

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

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

    КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Если маска под­се­ти 255.255.252.0 и IP-⁠адрес ком­пью­те­ра в сети 226.185.90.162, то номер ком­пью­те­ра в сети равен _____.

Зна­че­ние вы­ра­же­ния 2 · 216⁶ + 3 · 36⁹ − 432 за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 6. Сколь­ко цифр 5 со­дер­жит­ся в этой за­пи­си?

На чис­ло­вой пря­мой задан от­ре­зок A. Из­вест­но, что фор­му­ла

тож­де­ствен­но ис­тин­на при любых ве­ще­ствен­ных x и y. Какую наи­боль­шую длину может иметь от­ре­зок A?

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

F(n)  =  1 при n  =  1;

F(n)  =  n · F(n − 1), если n > 1.

Чему равно зна­че­ние вы­ра­же­ния F(2023) / F(2020)?

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

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

168

7

320

328

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

4 488

По­яс­не­ние. Из 4 чисел можно со­ста­вить 6 пар. В дан­ном слу­чае усло­ви­ям удо­вле­тво­ря­ют пары: 168 и 320, 168 и 7, 320 и 7, 328 и 7. Мак­си­маль­ную сумму дает пара 168 и 320  — 488.

Ответ:

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

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

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

Для ука­зан­ных вход­ных дан­ных от­ве­том будет число 14 (ладья про­хо­дит через клет­ки с чис­ла­ми −3, 6, 1, 7, 6, −3).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В этом слу­чае про­цес­сы могут вы­пол­нять­ся толь­ко по­сле­до­ва­тель­но.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Про­да­вец предо­став­ля­ет по­ку­па­те­лю, де­ла­ю­ще­му боль­шую за­куп­ку, скид­ку по сле­ду­ю­щим пра­ви­лам:

—  на каж­дый вто­рой товар сто­и­мо­стью боль­ше 50 руб­лей предо­став­ля­ет­ся скид­ка 25%;

—  общая сто­и­мость по­куп­ки со скид­кой округ­ля­ет­ся вверх до це­ло­го числа руб­лей;

—  по­ря­док то­ва­ров в спис­ке опре­де­ля­ет про­да­вец и де­ла­ет это так, чтобы общая сумма скид­ки была наи­мень­шей.

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

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

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

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

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

6

125

50

490

215

144

320 В дан­ном слу­чае товар сто­и­мо­стью 50 не участ­ву­ет в опре­де­ле­нии скид­ки, осталь­ные то­ва­ры про­дав­цу вы­год­но рас­по­ло­жить в таком по­ряд­ке цен: 490, 125, 215, 144, 320. Тогда скид­ка предо­став­ля­ет­ся на то­ва­ры сто­и­мо­стью 125 и 144. Сто­и­мость этих двух то­ва­ров со скид­кой со­ста­вит 201,75 руб­лей, после округ­ле­ния  — 202 рубля. Общая сто­и­мость по­куп­ки со­ста­вит:

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

Ответ:

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

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

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

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

3

1 2 3

5 12 4

6 9 7

Для ука­зан­ных дан­ных ис­ко­мая сумма равна 24, она со­от­вет­ству­ет та­ко­му рас­пре­де­ле­нию чисел по груп­пам: (1, 5, 6), (2, 4, 7), (3, 12, 9).

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

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

Ответ: