codeforces-scrape

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

1702D.md (2027B)


      1 Source: https://codeforces.com/problemset/problem/1702/D
      2 
      3 D. Not a Cheap 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 Let $s$ be a string of lowercase Latin letters. Its price is the sum of the indices of letters (an integer between 1 and 26) that are included in it. For example, the price of the string abca is $1+2+3+1=7$.
     22 
     23 The string $w$ and the integer $p$ are given. Remove the minimal number of letters from $w$ so that its price becomes less than or equal to $p$ and print the resulting string. Note that the resulting string may be empty. You can delete arbitrary letters, they do not have to go in a row. If the price of a given string $w$ is less than or equal to $p$, then nothing needs to be deleted and $w$ must be output.
     24 
     25 Note that when you delete a letter from $w$, the order of the remaining letters is preserved. For example, if you delete the letter e from the string test, you get tst.
     26 
     27 Input
     28 
     29 The first line of input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test. The following are descriptions of $t$ test cases.
     30 
     31 Each case consists of two lines.
     32 
     33 The first of them is the string $w$, it is non-empty and consists of lowercase Latin letters. Its length does not exceed $2\cdot10^5$.
     34 
     35 The second line contains an integer $p$ ($1 \le p \le 5\,200\,000$).
     36 
     37 It is guaranteed that the sum of string lengths $w$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 Output exactly $t$ rows, the $i$-th of them should contain the answer to the $i$-th set of input data. Print the longest string that is obtained from $w$ by deleting letters such that its price is less or equal to $p$. If there are several answers, then output any of them.
     42 
     43 Note that the empty string  — is one of the possible answers. In this case, just output an empty string.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 abca
     53 
     54 2
     55 
     56 abca
     57 
     58 6
     59 
     60 codeforces
     61 
     62 1
     63 
     64 codeforces
     65 
     66 10
     67 
     68 codeforces
     69 
     70 100
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 aa
     77 abc
     78 
     79 cdc
     80 codeforces
     81 ```