CodeCraft-20 (Div. 2) |
---|
Закончено |
У Васи есть строка $$$s$$$ длины $$$n$$$. Он решает применить к ней следующее преобразование:
Вася хочет выбрать такое $$$k$$$, чтобы строка, полученная в результате преобразования, была лексикографически минимальной возможной среди всех выборов $$$k$$$. Среди всех таких $$$k$$$ он хочет выбрать наименьшее. Так как он занят посещением Felicity 2020, он просит вашей помощи.
Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:
Каждый тест содержит несколько наборов входных данных.
Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 5000$$$). Далее следуют описания наборов входных данных.
Вторая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — длину строки $$$s$$$.
Третья строка каждого набора входных данных содержит строку $$$s$$$ из $$$n$$$ строчных букв латинского алфавита.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.
Для каждого набора входных данных выведите две строки:
В первой строке выведите лексикографически минимально возможную строку $$$s'$$$, получающуюся как результат преобразования.
Во второй строке выведите подходящее значение $$$k$$$ ($$$1 \leq k \leq n$$$), которое вы выбрали для преобрразования. Если несколько значений $$$k$$$ дают лексикографически минимальную строку, выведите минимальное $$$k$$$ среди них.
6 4 abab 6 qwerty 5 aaaaa 6 alaska 9 lfpbavjsm 1 p
abab 1 ertyqw 3 aaaaa 1 aksala 6 avjsmbpfl 5 p 1
В первом наборе тестовых данных примера, преобразование строки abab даст следующие результаты:
Лексикографически наименьшая строка, которую можно получить — это abab для $$$k = 1$$$ и $$$3$$$. Следовательно, наименьшее значение $$$k$$$ равно $$$1$$$.
Название |
---|