C - One More aab aba baa

コンテスト時間: 2021-08-21(土) 12:00 ~ 2021-08-21(土) 13:40 (100分) AtCoderホームへ戻る

C - One More aab aba baa 解説

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : $300$ 点

問題文

文字列 $S$ の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から $K$ 番目にくる文字列を求めてください。

「各文字を並べ替えて作ることが可能な文字列」とは？

「文字列 $A$ が文字列 $B$ の各文字を並べ替えて作ることが可能な文字列である」とは、任意の文字が文字列 $A$ と文字列 $B$ に同数含まれるということを指します。

制約

$1 \le |S| \le 8$
$S$ は英小文字のみからなる
$S$ の各文字を並べ替えてできる文字列は $K$ 種類以上存在する

入力

入力は以下の形式で標準入力から与えられる。

 $S$   $K$

出力

答えを出力せよ。

入力例 1 Copy

Copy

aab 2

出力例 1 Copy

Copy

aba

文字列 aab の各文字を並べ替えて作ることが可能な文字列は $\{$ aab, aba, baa $\}$ の $3$ つですが、このうち辞書順で前から $2$ 番目にくるものは aba です。

入力例 2 Copy

Copy

baba 4

出力例 2 Copy

Copy

baab

入力例 3 Copy

Copy

ydxwacbz 40320

出力例 3 Copy

Copy

zyxwdcba

Score : $300$ points

Problem Statement

Find the $K$ -th lexicographically smallest string among the strings that are permutations of a string $S$ .

What is a permutation of a string?

A string $A$ is said to be a permutation of a string $B$ when any character occurs the same number of times in $A$ and $B$ .

Constraints

$1 \le |S| \le 8$
$S$ consists of lowercase English letters.
There are at least $K$ distinct strings that are permutations of $S$ .

Input

Input is given from Standard Input in the following format:

 $S$   $K$

Output

Print the answer.

Sample Input 1 Copy

Copy

aab 2

Sample Output 1 Copy

Copy

aba

There are three permutations of a string aab: $\{$ aab, aba, baa $\}$ . The $2$ -nd lexicographically smallest of them is aba.

Sample Input 2 Copy

Copy

baba 4

Sample Output 2 Copy

Copy

baab

Sample Input 3 Copy

Copy

ydxwacbz 40320

Sample Output 3 Copy

Copy

zyxwdcba