1316B.md (2779B)
1 Source: https://codeforces.com/problemset/problem/1316/B 2 3 B. String Modification 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Vasya has a string $s$ of length $n$. He decides to make the following modification to the string: 22 23 1. Pick an integer $k$, ($1 \leq k \leq n$). 24 2. For $i$ from $1$ to $n-k+1$, reverse the substring $s[i:i+k-1]$ of $s$. For example, if string $s$ is qwer and $k = 2$, below is the series of transformations the string goes through: 25 * qwer (original string) 26 * wqer (after reversing the first substring of length $2$) 27 * weqr (after reversing the second substring of length $2$) 28 * werq (after reversing the last substring of length $2$)Hence, the resulting string after modifying $s$ with $k = 2$ is werq. 29 30 Vasya wants to choose a $k$ such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of $k$. Among all such $k$, he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help. 31 32 A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds: 33 34 * $a$ is a prefix of $b$, but $a \ne b$; 35 * in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$. 36 37 Input 38 39 Each test contains multiple test cases. 40 41 The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows. 42 43 The first line of each test case contains a single integer $n$ ($1 \le n \le 5000$) — the length of the string $s$. 44 45 The second line of each test case contains the string $s$ of $n$ lowercase latin letters. 46 47 It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$. 48 49 Output 50 51 For each testcase output two lines: 52 53 In the first line output the lexicographically smallest string $s'$ achievable after the above-mentioned modification. 54 55 In the second line output the appropriate value of $k$ ($1 \leq k \leq n$) that you chose for performing the modification. If there are multiple values of $k$ that give the lexicographically smallest string, output the smallest value of $k$ among them. 56 57 Example 58 59 Input 60 61 ``` 62 6 63 4 64 abab 65 6 66 qwerty 67 5 68 aaaaa 69 6 70 alaska 71 9 72 lfpbavjsm 73 1 74 p 75 ``` 76 77 Output 78 79 ``` 80 abab 81 1 82 ertyqw 83 3 84 aaaaa 85 1 86 aksala 87 6 88 avjsmbpfl 89 5 90 p 91 1 92 ``` 93 94 Note 95 96 In the first testcase of the first sample, the string modification results for the sample abab are as follows : 97 98 * for $k = 1$ : abab 99 * for $k = 2$ : baba 100 * for $k = 3$ : abab 101 * for $k = 4$ : baba 102 103 The lexicographically smallest string achievable through modification is abab for $k = 1$ and $3$. Smallest value of $k$ needed to achieve is hence $1$.