Украинские Олимпиады
Украинские Олимпиады по Информатике
по Информатике

Соревнования

Информация
Добро пожаловать
Гостевая книга
Обратная связь
О сайте

ACM-олимпиада
Новости
Правила
Задачи
Сдать задачу
Таблица результатов

IOI-олимпиада
Новости
Правила
Последние задачи
Последние результаты
Архив

"Трудно-решаемая" задача
Новости
Правила
Последняя задача
Последние результаты
Архив

Логические игры
Новости
Правила
Виды игр
Последний турнир
Архив

Викторина
Новости
Правила
Последняя викторина
Архив

 
 
Черновцы'2002, I тур

Абракадабра

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

Строка P называется ротацией строки S, если она образована циклическим сдвигом символов S, т.е. если S=a1a2aN, где aii–ый символ строки S, то P=apap+1aNa1ap-1, где 1£p£N. Рассмотрим таблицу M размера N´N, строками которой есть все ротации строки S, отсортированные в лексикографическом (словарном) порядке по возрастанию.

Пусть строка L есть последний столбик таблицы M. Прямое преобразование получает на вход строку S, выдает строку L и число K— номер строки таблицы M, который содержит строку S. (Если таких строк несколько, выдается номер любой из них).

Для S="abraka" таблица M изображена на рисунке. Строка S находится во второй строке таблицы M, L="karaab".

Задача

Напишите программу ABRAKA, которая выполняет обратное преобразование, т.е. получает на вход строку L и число K, и выдает строку S.

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

Первая строка входного файла ABRAKA.DAT содержит два целых числа: K и N, 1£N£30000, 1£K£N. Вторая строка содержит N символов строки L— маленьких латинских букв.

Пример входных данных
2 6
karaab
Выходные данные

Единственная строка выходного файла ABRAKA.SOL должна содержать строку S.

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

 

Сборник

Олимпиады
Международные
Всесоюзные
Всеукраинские (IV этап)
Разные...

Всеукраинские олимпиады
1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003

Отборочные сборы
1992 1993 1994 1996 1997 1998 1999 2000 2001 2002

Международные олимпиады
1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002

Всесоюзные олимпиады
1988 1989 1990 1991 1992

Информация
Список ссылок
Литература
Статьи
Рассылки
Интервью

© Разработано рабочей группой UOI 1998-2003 гг.