codeforces-scrape

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

1886C.md (1941B)


      1 Source: https://codeforces.com/problemset/problem/1886/C
      2 
      3 C. Decreasing String
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 Recall that string $a$ is lexicographically smaller than string $b$ if $a$ is a prefix of $b$ (and $a \ne b$), or there exists an index $i$ ($1 \le i \le \min(|a|, |b|)$) such that $a_i \lt b_i$, and for any index $j$ ($1 \le j \lt i$) $a_j = b_j$.
     22 
     23 Consider a sequence of strings $s_1, s_2, \dots, s_n$, each consisting of lowercase Latin letters. String $s_1$ is given explicitly, and all other strings are generated according to the following rule: to obtain the string $s_i$, a character is removed from string $s_{i-1}$ in such a way that string $s_i$ is lexicographically minimal.
     24 
     25 For example, if $s_1 = \mathrm{dacb}$, then string $s_2 = \mathrm{acb}$, string $s_3 = \mathrm{ab}$, string $s_4 = \mathrm{a}$.
     26 
     27 After that, we obtain the string $S = s_1 + s_2 + \dots + s_n$ ($S$ is the concatenation of all strings $s_1, s_2, \dots, s_n$).
     28 
     29 You need to output the character in position $pos$ of the string $S$ (i. e. the character $S_{pos}$).
     30 
     31 Input
     32 
     33 The first line contains one integer $t$ — the number of test cases ($1 \le t \le 10^4$).
     34 
     35 Each test case consists of two lines. The first line contains the string $s_1$ ($1 \le |s_1| \le 10^6$), consisting of lowercase Latin letters. The second line contains the integer $pos$ ($1 \le pos \le \frac{|s_1| \cdot (|s_1| +1)}{2}$). You may assume that $n$ is equal to the length of the given string ($n = |s_1|$).
     36 
     37 Additional constraint on the input: the sum of $|s_1|$ over all test cases does not exceed $10^6$.
     38 
     39 Output
     40 
     41 For each test case, print the answer — the character that is at position $pos$ in string $S$. Note that the answers between different test cases are not separated by spaces or line breaks.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 cab
     51 
     52 6
     53 
     54 abcd
     55 
     56 9
     57 
     58 x
     59 
     60 1
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 abx
     67 ```