Минимальный лексикографически циклический сдвиг перестановки
Первоисточник: Онлайн-олимпиады школьников, 2007 год, 9 тренировка, базовый уровень, задача B
URL первоисточника: neerc.ifmo.ru/school/io
Задачу добавил: ant.ermilov
Успешно сдано решений: 5
Перестановкой порядка n называется последовательность из попарно различных целых положительных чисел p1, p2, ..., pn, где каждое 1<= pi <= n. Будем говорить, что перестановка q1, q2, ..., qn лексикографически меньше перестановки p1, p2, ..., pn, если существует такое i, что qi<pi, а для любого j<i qi=pi.Циклическим сдвигом на k перестановки p1, p2, ..., pn называется перестановка pk+1, pk+2, ..., pn , p1, ..., pk.
Ваша задача состоит в том, чтобы найти наименьший лексикографический сдвиг заданной перестановки.
Формат входного файла(input.txt):
В первой строке задан порядок n перестановки (1<=n<=100000). Во второй строке содержатся элементы перестановки.
Формат выходного файла(output.txt):
Выведите n чисел - минимальную лексикографически перестановку, являющуюся циклическим сдвигом исходной.
Пример
| input.txt | output.txt |
| 3 3 2 1 | 1 3 2 |
Решения по задаче А (на 00:00 230610), в порядке ухудшения результата:
1. shtserg_2 (40 баллов).
2 shtserg_1 (22 балла).