Файл входного файла:	restore.in
Файл выходного файла:	restore.out
Ограничение по памяти:	64 MB
Ограничение по времени:	2 s

Описание

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

Рассмотрим, что происходит при таком преобразовании со строкой «abraca»:

Итак, в результате мы получили строку «caraab». В дополнение к найденной строке мы определяем также позицию исходной строки в отсортированном списке циклических сдвигов (в данном случае 2). Оказывается, что исходя из этих двух данных, первоначальная строка восстанавливается однозначно. Напишите программу, которая сделает это.

Формат входных данных

В первой строке входного файла записано целое число k — номер исходной строки в отсортированном списке циклических сдвигов. На следующей строке записан результат преобразования. Входные данные таковы, что исходная строка всегда существует. Сама строка состоит из символов с кодами от 33 до 255. Длина заданной строки не превосходит 10 ⁵ .

Формат выходных данных

В выходной файл выведите исходную строку.

Примеры:

ввод	вывод
2 caraab	abraca

34 eehnyollwwhvnewoeoriretdtdaaneanogb	whenwehavetolearntodowelearnbydoing

5 bbccaabbaaaaaa	abacabaabacaba

Added: admin
Difficulty: 4.44206124376
Accepted: 5
Submitted: 65
Источник задачи: XX городская олимпиада школьников Санкт-Петербурга по информатике, 6 марта 2005 г.

Analyze this 3 Комментарии