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

Работа еще не завершена, поэтому пока что он умеет обрабатывать строки только одним способом. Строка, которую ему передают на ввод, должна состоять из \(2^k\) символов, а программа обработки этой строки — из \(2^k \ − \ 1\) чисел, каждое из которых является нулем или единицей.

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

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

Так, например, если на вход сопроцессору подана строка «abcd» и программа (0, 1, 1), то результатом обработки будет строка «dcab».

Вам поступило предложение принять участие в его тестировании. Отказаться от такого лестного предложения вы не смогли, поэтому теперь вам необходимо научиться составлять программу для сопроцессора, с помощью которой он преобразует строку \(S\) в строку \(T\), или же определять, что такой программы не существует.

На прошлом уроке английского Пете задали домашнее задание. Оно заключалось в разгадывании ребусов. Каждый ребус — это последовательность картинок. С двух сторон от каждой картинки могут располагаться апострофы. Каждая картинка обозначает некоторое слово. Предположим, что перед некоторой картинкой нарисовано \(i\) апострофов, а после нее \(j\) апострофов. Это значит, что у слова, которое сопоставляется картинке, необходимо убрать \(i\) букв с начала и \(j\) с конца, а оставшуюся его часть записать вместо картинки и апострофов. Так необходимо сделать с каждой картинкой и окружающими ее апострофами. После этого нужно «склеить» получившиеся кусочки в одно слово. Оно и будет разгадкой ребуса.

У Пети нет проблем с тем, чтобы сопоставить каждой картинке слово. Но ему очень лень заниматься отбрасыванием лишних букв и склеиванием слов. Поэтому он попросил вас помочь ему. Дана строка, которая состоит из маленьких латинских букв, апострофов (символов с кодом 39), а также пробелов, которые разделяют слова. Апостроф относиться к некоторому слову, если между ними нет пробела. Если апостроф стоит слева от слова, то у него необходимо убрать одну букву с начала, если справа — с конца. Потом необходимо склеить все слова в одно.

Например, пусть дана строчка «team ’ ’ ’ ’ school ’ ’ olympiad’ ’ ’». В первом слове ничего изменять не надо, так как к нему не относится ни один апостроф. Во втором необходимо убрать первые четыре буквы и получить «ol», из третьего слова получится «ymp». После скеливания трех кусочков получим строку «teamolymp».

Каждый год профессор Иванов ездит в Африку с целью изучить племена, которые там проживают. В этом году он ездил в гости к племени тив. Профессор довольно быстро научился понимать их язык, выучил многие их обряды, однако, он никак не мог понять записанные цифрами тив числа. Как и мы, члены племени используют позиционную систему счисления с основанием 10. Но цифры в племени тив обозначают символами, не похожими на обычные цифры от 0 до 9.

Профессор обозначил эти символы буквами от ‘a’ до ‘j’, но не может понять, какой цифре соответствует какой символ. Тогда вождь племени дал ему список из n неотрицательных чисел, записанных без ведущих нулей, и сказал, что числа в нем отсортированы строго по возрастанию.

Помогите профессору восстановить по этому списку какое-нибудь соответствие символов цифрам.

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

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

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

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

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

После анализа дисков было установлено, что они использовались в XXI веке по летоисчислению, использовавшемуся древней цивилизацией — так называемому «григорианскому» календарю — год продолжительностью 365 дней, разделялся по нему на двенадцать месяцев. Второй месяц в году имел продолжительность двадцать восемь дней, первый, третий, пятый, седьмой, восьмой, десятый и двенадцатый — тридцать один день, остальные — тридцать дней. В особые года, номер которых делился на четыре и не делился на сто, либо делился на четыреста, второй месяц длился двадцать девять дней. Веком номер \(i\) назывался период с \(100 \cdot (i \ − \ 1) + 1\) года по \(100 \cdot i\).

Так как достоверно не известно, в каком порядке представители древней цивилизации записывали даты, вам, как главному специалисту по григорианскому календарю, поручили провести исследование — установить, каким датам в XXI веке могла соответствовать надпись, в предположении, что одно из чисел соответствует дню в месяце (дни в каждом месяце нумеровались с единицы), еще одно из чисел — номеру месяца (месяцы также нумеровались с единицы), и еще одно число — последним двум цифрам года в XXI веке григорианского календаря.

По заданной надписи на диске выясните, каким датам в XXI веке она могла соответствовать.