1328B.md (1807B)
1 Source: https://codeforces.com/problemset/problem/1328/B 2 3 B. K-th Beautiful String 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 For the given integer $n$ ($n \gt 2$) let's write down all the strings of length $n$ which contain $n-2$ letters 'a' and two letters 'b' in lexicographical (alphabetical) order. 22 23 Recall that the string $s$ of length $n$ is lexicographically less than string $t$ of length $n$, if there exists such $i$ ($1 \le i \le n$), that $s_i \lt t_i$, and for any $j$ ($1 \le j \lt i$) $s_j = t_j$. The lexicographic comparison of strings is implemented by the operator < in modern programming languages. 24 25 For example, if $n=5$ the strings are (the order does matter): 26 27 1. aaabb 28 2. aabab 29 3. aabba 30 4. abaab 31 5. ababa 32 6. abbaa 33 7. baaab 34 8. baaba 35 9. babaa 36 10. bbaaa 37 38 It is easy to show that such a list of strings will contain exactly $\frac{n \cdot (n-1)}{2}$ strings. 39 40 You are given $n$ ($n \gt 2$) and $k$ ($1 \le k \le \frac{n \cdot (n-1)}{2}$). Print the $k$-th string from the list. 41 42 Input 43 44 The input contains one or more test cases. 45 46 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test. Then $t$ test cases follow. 47 48 Each test case is written on the the separate line containing two integers $n$ and $k$ ($3 \le n \le 10^5, 1 \le k \le \min(2\cdot10^9, \frac{n \cdot (n-1)}{2})$. 49 50 The sum of values $n$ over all test cases in the test doesn't exceed $10^5$. 51 52 Output 53 54 For each test case print the $k$-th string from the list of all described above strings of length $n$. Strings in the list are sorted lexicographically (alphabetically). 55 56 Example 57 58 Input 59 60 ``` 61 7 62 5 1 63 5 2 64 5 8 65 5 10 66 3 1 67 3 2 68 20 100 69 ``` 70 71 Output 72 73 ``` 74 aaabb 75 aabab 76 baaba 77 bbaaa 78 abb 79 bab 80 aaaaabaaaaabaaaaaaaa 81 ```