codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```