問題一覧 > 通常問題

No.3290 Encrypt Failed, but Decrypt Succeeded

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 67
作問者 : kona0001 / テスター : tobisatis RyosukeFukatani koba-e964 ir5 drken1215
お気に入りにしたユーザー ProblemId : 12640 / 自分の提出
問題文最終更新日: 2025-09-24 01:40:31
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 485 (順位表) の他の問題:

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 a with 1, b with 2, ..., and z with 26.

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 0 to 9
  • 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.

  • aabcd
  • aawd
  • alcd
  • kbcd
  • kwd

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もしくは右上の雲マークをクリックしてアカウントを作成してください。