No.3290 Encrypt Failed, but Decrypt Succeeded
Problem Statement
Yuki is shy. Not wanting anyone to see what he has written, Yuki came up with the following cipher.
- For each of the $26$ lowercase English letters, replace
awith1,bwith2, ..., andzwith26.
Using this procedure, Yuki encrypted a string $s$ consisting of lowercase English letters and obtained a string $t$ of length $N$. However, he carelessly forgot to put separators between the numbers, so the string obtained on decryption is no longer uniquely determined. Therefore, he decided to use lexicographic order to uniquely determine the decrypted string.
Among the possible strings $s^{\prime}$ that yield $t$ when encrypted, find the $K$-th one in lexicographic order.
Constraints
- $1 \le N \le 3 \times 10^5$
- $1 \le K \le 10^{18}$
- $N$ and $K$ are integers
- $t$ is a string of length $N$ consisting of digits from
0to9 - There are at least $K$ distinct strings that yield $t$ when encrypted
Input
The input is given from standard input in the following format.
$N\ K$ $t$
Output
Among the possible strings $s^{\prime}$ that yield $t$ when encrypted, output the $K$-th string in lexicographic order. Print a newline at the end.
Sample
Sample 1
Input
5 4 11234
Output
kbcd
The possible strings $s^{\prime}$ that yield the string 11234 when encrypted are as follows.
aabcdaawdalcdkbcdkwd
Among these, the $4$-th string in lexicographic order is kbcd, so this is the correct answer.
Sample 2
Input
8 1 11111111
Output
aaaaaaaa
Sample 3
Input
50 225580 19211651831129618179129192093524169112941539152119
Output
supercalifragilisticexpialidocious
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
kona0001
drken1215