Сколь­ко еди­ниц в дво­ич­ной за­пи­си шест­на­дца­те­рич­но­го числа E0F3₁₆?

Миша за­пол­нял таб­ли­цу ис­тин­но­сти функ­ции (x ∧ ¬y) ∨ (x ≡ z) ∨ ¬w, но успел за­пол­нить лишь фраг­мент из трёх раз­лич­ных её строк, даже не ука­зав, ка­ко­му столб­цу таб­ли­цы со­от­вет­ству­ет каж­дая из пе­ре­мен­ных w, x, y, z.

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

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

При­мер. Функ­ция за­да­на вы­ра­же­ни­ем ¬x ∨ y, за­ви­ся­щим от двух пе­ре­мен­ных, а фраг­мент таб­ли­цы имеет сле­ду­ю­щий вид.

В этом слу­чае пер­во­му столб­цу со­от­вет­ству­ет пе­ре­мен­ная y, а вто­ро­му столб­цу  — пе­ре­мен­ная x. В от­ве­те сле­ду­ет на­пи­сать yx.

На ри­сун­ке слева изоб­ра­же­на схема дорог N-⁠ского рай­о­на. В таб­ли­це звёздоч­кой обо­зна­че­но на­ли­чие до­ро­ги из од­но­го населённого пунк­та в дру­гой. От­сут­ствие звёздоч­ки озна­ча­ет, что такой до­ро­ги нет.

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

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

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г, Д, Е, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для букв А, Б, В, Г ис­поль­зо­ва­ли ко­до­вые слова 100, 101, 00, 01 со­от­вет­ствен­но. Для двух остав­ших­ся букв  — Д и Е  — коды не­из­вест­ны.

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

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

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

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

2)  К этой за­пи­си до­пи­сы­ва­ют­ся спра­ва ещё два раз­ря­да по сле­ду­ю­ще­му пра­ви­лу: если N чётное, в конец числа (спра­ва) до­пи­сы­ва­ют­ся два нуля, в про­тив­ном слу­чае спра­ва до­пи­сы­ва­ют­ся две еди­ни­цы. На­при­мер, дво­ич­ная за­пись 1001 числа 9 будет пре­об­ра­зо­ва­на в 100111.

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

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

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

При­ме­ча­ние: знак $ обо­зна­ча­ет аб­со­лют­ную ад­ре­са­цию.

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

Му­зы­каль­ный фраг­мент был за­пи­сан в фор­ма­те сте­рео (двух­ка­наль­ная за­пись), оциф­ро­ван и со­хранён в виде файла без ис­поль­зо­ва­ния сжа­тия дан­ных. Раз­мер по­лу­чен­но­го файла без учёта раз­ме­ра за­го­лов­ка файла  — 48 Мбайт. Затем тот же му­зы­каль­ный фраг­мент был за­пи­сан по­втор­но в фор­ма­те моно и оциф­ро­ван с раз­ре­ше­ни­ем в 1,5 раза выше и ча­сто­той дис­кре­ти­за­ции в 3 раза мень­ше, чем в пер­вый раз. Сжа­тие дан­ных не про­из­во­ди­лось. Ука­жи­те раз­мер в Мбайт файла, по­лу­чен­но­го при по­втор­ной за­пи­си. В от­ве­те за­пи­ши­те толь­ко целое число, еди­ни­цу из­ме­ре­ния пи­сать не нужно. Ис­ко­мый объём не учи­ты­ва­ет раз­ме­ра за­го­лов­ка файла.

Вася со­став­ля­ет 4-⁠бук­вен­ные слова, в ко­то­рых есть толь­ко буквы Б, Е, Л, К, А, причём буква Б ис­поль­зу­ет­ся в каж­дом слове ровно 1 раз. Каж­дая из дру­гих до­пу­сти­мых букв может встре­чать­ся в слове любое ко­ли­че­ство раз или не встре­чать­ся со­всем. Сло­вом счи­та­ет­ся любая до­пу­сти­мая по­сле­до­ва­тель­ность букв, не обя­за­тель­но осмыс­лен­ная. Сколь­ко су­ще­ству­ет таких слов, ко­то­рые может на­пи­сать Вася?

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­сан ре­кур­сив­ный ал­го­ритм F.

За­пи­ши­те под­ряд без про­бе­лов и раз­де­ли­те­лей все числа, ко­то­рые будут вы­ве­де­ны на экран при вы­пол­не­нии вы­зо­ва F(7). Числа долж­ны быть за­пи­са­ны в том же по­ряд­ке, в ко­то­ром они вы­во­дят­ся на экран.

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

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

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

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 25 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы из 7-⁠сим­воль­но­го на­бо­ра: С, Д, А, М, Е, Г, Э. В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Кроме соб­ствен­но па­ро­ля, для каж­до­го поль­зо­ва­те­ля в си­сте­ме хра­нят­ся до­пол­ни­тель­ные све­де­ния, для чего вы­де­ле­но целое число байт; это число одно и то же для всех поль­зо­ва­те­лей. Для хра­не­ния све­де­ний о 100 поль­зо­ва­те­лях по­тре­бо­ва­лось 2400 байт.

Сколь­ко байт вы­де­ле­но для хра­не­ния до­пол­ни­тель­ных све­де­ний об одном поль­зо­ва­те­ле? В от­ве­те за­пи­ши­те толь­ко целое число – ко­ли­че­ство байт.

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

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

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

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

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

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

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

Цикл

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

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

    КОНЕЦ ПОКА

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

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

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

НА­ЧА­ЛО

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

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

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

    КОНЕЦ ЕСЛИ

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

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

    КОНЕЦ ЕСЛИ

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

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

    КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

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

Ка­ко­ва длина са­мо­го длин­но­го пути из го­ро­да А в город М? Дли­ной пути счи­тать ко­ли­че­ство дорог, со­став­ля­ю­щих этот путь.

Зна­че­ние ариф­ме­ти­че­ско­го вы­ра­же­ния 9⁸ · 3²⁰ − 3¹⁰ − 3 за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 3. Сколь­ко цифр 2 со­дер­жит­ся в этой за­пи­си?

В языке за­про­сов по­ис­ко­во­го сер­ве­ра для обо­зна­че­ния ло­ги­че­ской опе­ра­ции «ИЛИ» ис­поль­зу­ет­ся сим­вол «|», а для обо­зна­че­ния ло­ги­че­ской опе­ра­ции «И»  — сим­вол «&».

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

Какое ко­ли­че­ство стра­ниц (в сот­нях тысяч) будет най­де­но по за­про­су Фи­зи­ка & Квант?

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

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

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

В про­грам­ме ис­поль­зу­ет­ся од­но­мер­ный це­ло­чис­лен­ный мас­сив A с ин­дек­са­ми от 0 до 11. Зна­че­ния эле­мен­тов равны 14, 13, 15, 8, 4, 12, 30, 21, 22, 16, 5, 9 со­от­вет­ствен­но, т. е. A[0] = 14, A[1] = 13 и т. д. Опре­де­ли­те зна­че­ние пе­ре­мен­ной s после вы­пол­не­ния сле­ду­ю­ще­го фраг­мен­та этой про­грам­мы (за­пи­сан­но­го ниже на пяти язы­ках про­грам­ми­ро­ва­ния).

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

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

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

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

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

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

Про­грам­ма для Вы­чис­ли­те­ля  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 1 ре­зуль­та­том яв­ля­ет­ся число 22 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 10 и не со­дер­жит числа 15?

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

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x₁, x₂, ...x₉, y₁, y₂, ...y₉, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x₁ → (x₂ ∧ y₂)) ∧ (y₁ → y₂) = 1

(x₂ → (x₃ ∧ y₃)) ∧ (y₂ → y₃) = 1

                        …

(x₈ → (x₉ ∧ y₉)) ∧ (y₈ → y₉) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x₁, x₂, ... x₉, y₁, y₂, ...y₉, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Тре­бо­ва­лось на­пи­сать про­грам­му, ко­то­рая по­лу­ча­ет на вход на­ту­раль­ное число N, не пре­вос­хо­дя­щее 10⁹, и вы­во­дит число, рав­ное ко­ли­че­ству цифр 2 в де­ся­тич­ной за­пи­си числа N. Про­грам­мист на­пи­сал про­грам­му не­пра­виль­но. Ниже эта на­пи­сан­ная им про­грам­ма для Ва­ше­го удоб­ства при­ве­де­на на пяти язы­ках про­грам­ми­ро­ва­ния.

По­сле­до­ва­тель­но вы­пол­ни­те сле­ду­ю­щее.

1.  На­пи­ши­те, что вы­ве­дет эта про­грам­ма при вводе числа 324.

2.  При­ве­ди­те при­мер вход­но­го числа N, при ко­то­ром при­ведённая про­грам­ма, не­смот­ря на ошиб­ки, выдаёт вер­ный ответ.

3.  Най­ди­те до­пу­щен­ные про­грам­ми­стом ошиб­ки и ис­правь­те их.

Ис­прав­ле­ние ошиб­ки долж­но за­тра­ги­вать толь­ко стро­ку, в ко­то­рой на­хо­дит­ся ошиб­ка. Для каж­дой ошиб­ки:

1)  вы­пи­ши­те стро­ку, в ко­то­рой сде­ла­на ошиб­ка;

2)  ука­жи­те, как ис­пра­вить ошиб­ку, т. е. при­ве­ди­те пра­виль­ный ва­ри­ант стро­ки.

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

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

Дан це­ло­чис­лен­ный мас­сив из 30 эле­мен­тов. Эле­мен­ты мас­си­ва могут при­ни­мать целые зна­че­ния от 0 до 10 000 вклю­чи­тель­но. Опи­ши­те на одном из язы­ков про­грам­ми­ро­ва­ния ал­го­ритм, ко­то­рый на­хо­дит сумму эле­мен­тов мас­си­ва, боль­ших 100 и при этом не крат­ных 4, а затем за­ме­ня­ет каж­дый такой эле­мент на число, рав­ное най­ден­ной сумме. Га­ран­ти­ру­ет­ся, что хотя бы один такой эле­мент в мас­си­ве есть. В ка­че­стве ре­зуль­та­та не­об­хо­ди­мо вы­ве­сти изменённый мас­сив, каж­дый эле­мент вы­во­дит­ся с новой строч­ки. На­при­мер, для ис­ход­но­го мас­си­ва из шести эле­мен­тов:

101

128

6

105

4

18

про­грам­ма долж­на вы­ве­сти сле­ду­ю­щий мас­сив:

206

128

6

206

4

18

Ис­ход­ные дан­ные объ­яв­ле­ны так, как по­ка­за­но ниже на при­ме­рах для пяти язы­ков про­грам­ми­ро­ва­ния. За­пре­ща­ет­ся ис­поль­зо­вать пе­ре­мен­ные, не опи­сан­ные ниже, но раз­ре­ша­ет­ся не ис­поль­зо­вать не­ко­то­рые из опи­сан­ных пе­ре­мен­ных.

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

По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, т. е. пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 68 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней; 1 ≤ S ≤ 67.

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

Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.

Вы­пол­ни­те сле­ду­ю­щие за­да­ния.

За­да­ние 1

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

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

За­да­ние 2

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

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

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

Для каж­до­го ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.

За­да­ние 3

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

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

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

Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вани. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при этой вы­иг­рыш­ной стра­те­гии Вани (в виде ри­сун­ка или таб­ли­цы). На рёбрах де­ре­ва ука­зы­вай­те, кто де­ла­ет ход; в узлах  — ко­ли­че­ство кам­ней в куче. Де­ре­во не долж­но со­дер­жать пар­тии, не­воз­мож­ные при ре­а­ли­за­ции вы­иг­ры­ва­ю­щим иг­ро­ком своей вы­иг­рыш­ной стра­те­гии. На­при­мер, пол­ное де­ре­во игры не яв­ля­ет­ся вер­ным от­ве­том на это за­да­ние.

Дана по­сле­до­ва­тель­ность N целых по­ло­жи­тель­ных чисел. Рас­смат­ри­ва­ют­ся все пары эле­мен­тов по­сле­до­ва­тель­но­сти, раз­ность ко­то­рых чётна, и в этих парах, по край­ней мере, одно из чисел пары де­лит­ся на 19. По­ря­док эле­мен­тов в паре не­ва­жен. Среди всех таких пар нужно найти и вы­ве­сти пару с мак­си­маль­ной сум­мой эле­мен­тов. Если оди­на­ко­вую мак­си­маль­ную сумму имеет не­сколь­ко пар, можно вы­ве­сти любую из них. Если под­хо­дя­щих пар в по­сле­до­ва­тель­но­сти нет, нужно вы­ве­сти два нуля.

Опи­са­ние вход­ных и вы­ход­ных дан­ных.

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

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

5

38

12

57

16

57

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

57 57

По­яс­не­ние. Из дан­ных пяти чисел можно со­ста­вить три раз­лич­ные пары, удо­вле­тво­ря­ю­щие усло­вию: (38, 12), (38, 16), (57, 57). Наи­боль­шая сумма по­лу­ча­ет­ся в паре (57, 57). Эта пара до­пу­сти­ма, так как число 57 встре­ча­ет­ся в ис­ход­ной по­сле­до­ва­тель­но­сти два­жды.

Тре­бу­ет­ся на­пи­сать эф­фек­тив­ную по вре­ме­ни и па­мя­ти про­грам­му для ре­ше­ния опи­сан­ной за­да­чи.

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если при од­но­вре­мен­ном уве­ли­че­нии ко­ли­че­ства эле­мен­тов по­сле­до­ва­тель­но­сти n и па­ра­мет­ра m в k раз время ра­бо­ты про­грам­мы уве­ли­чи­ва­ет­ся не более чем в k раз.

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если па­мять, не­об­хо­ди­мая для хра­не­ния всех пе­ре­мен­ных про­грам­мы, не пре­вы­ша­ет 4 ки­ло­бай­та и не уве­ли­чи­ва­ет­ся с ро­стом n.

Мак­си­маль­ная оцен­ка за пра­виль­ную (не со­дер­жа­щую син­так­си­че­ских оши­бок и да­ю­щую пра­виль­ный ответ при любых до­пу­сти­мых вход­ных дан­ных) про­грам­му, эф­фек­тив­ную по вре­ме­ни и па­мя­ти,  — 4 балла. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, воз­мож­но, не­эф­фек­тив­ную по па­мя­ти или время вы­пол­не­ния ко­то­рой су­ще­ствен­но за­ви­сит от ве­ли­чи­ны m,  — 3 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, не удо­вле­тво­ря­ю­щую тре­бо­ва­ни­ям эф­фек­тив­но­сти,  — 2 балла.

Вы мо­же­те сдать одну про­грам­му или две про­грам­мы ре­ше­ния за­да­чи (на­при­мер, одна из про­грамм может быть менее эф­фек­тив­на). Если Вы сда­ди­те две про­грам­мы, то каж­дая из них будет оце­ни­вать­ся не­за­ви­си­мо от дру­гой, ито­го­вой ста­нет бо́льшая из двух оце­нок.

Перед тек­стом про­грам­мы обя­за­тель­но крат­ко опи­ши­те ал­го­ритм ре­ше­ния. Ука­жи­те ис­поль­зо­ван­ный язык про­грам­ми­ро­ва­ния и его вер­сию.