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