1488: Танець рядка

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 18
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Дано рядок \(S = s_1 , s_2 , ...s_n\) . Вам потрiбно зробити з ним один танцювальний рух такий, щоб вiн став лексикографiчно найменшим. Пiд танцювальним рухом будемо розумiти рiвно один розворот пiдрядка в рядку \(S\).

Формально кажучи, необхiдно вибрати пару iндексiв \(x, y\) \((1 \le x \le y \le n)\), а потiм змiнити порядок символiв з iндексами вiд \(x\) до \(y\) включно на протилежний. Тобто пiдрядок \(s_x , s_{x+1} ...s_y\) замiнюється на \(s_y , s_{y−1} , ...s_x \).

Ваша мета — отримати лексикографiчно найменший рядок iз можливих.

Формат вхідних даних

Перший рядок мiстить кiлькiсть \(T\) \((1 \le T \le 10^5 )\) наборiв вхiдних даних. Кожний набiр вхiдних даних розташований в окремому рядку вхiдного потоку i складається з одного непустого рядка \(S\). Кожен символ рядку \(S\) — мала буква англiйського алфавiта (вiд \(a\) до \(z\)). Сума довжин рядкiв \(S\) по всiм наборам вхiдних даних не перевищує \(10^6 \).

Формат вихідних даних

Для кожного набору вхiдних даних виведiть один рядок з двома цiлими числами \(x\) i \(y\). Якщо iснує декiлька оптимальних варiантiв вiдповiдей, виведiть будь-який iз них.

Приклад вхідних даних

1
abacaba

Приклад вихідних даних

2 7

Коментарі

Ще немає коментарів.