No.1630 Sorting Integers (Greater than K)
タグ : / 解いたユーザー数 98
作問者 :
とりゐ
/ テスター :
re_re0101
karinohito
Problem Statement
There are $N$ positive integers of $1$ digit. Among them, there are $c_i$ copies of $i$ $(1\leq i\leq9)$. Rearrange these $N$ integers and regard the result as an $N$-digit base-$10$ integer $M$. Find the smallest $M$ greater than $K$.
Input
$N\ K$ $c_1\ c_2\ c_3\ c_4\ c_5\ c_6\ c_7\ c_8\ c_9$
- $1\leq N\leq 500000$
- $1\leq K\leq 10^{500001}$
- $c_i\geq 0$
- $\displaystyle \sum _{i=1} ^9 c_i=N$
- All inputs are integers.
Output
If there exists an $M$ greater than $K$, print the minimum such value; otherwise, print -1.
Sample
Sample 1
Input
3 200 1 1 1 0 0 0 0 0 0
Output
213
Each of $1,2,3$ appears $1$ time, and the possible values of $M$ are $123,132,213,231,312,321$. The smallest $M$ greater than $200$ is $213$.
Sample 2
Input
3 213 1 1 1 0 0 0 0 0 0
Output
231
Each of $1,2,3$ appears $1$ time, and the possible values of $M$ are $123,132,213,231,312,321$. The smallest $M$ greater than $213$ is $231$.
Sample 3
Input
3 400 1 1 1 0 0 0 0 0 0
Output
-1
Each of $1,2,3$ appears $1$ time, and the possible values of $M$ are $123,132,213,231,312,321$. There is no $M$ greater than $400$.
Sample 4
Input
3 1 0 3 0 0 0 0 0 0 0
Output
222
There are $3$ copies of $2$, and the only possible value of $M$ is $222$. The smallest $M$ greater than $1$ is $222$.
Sample 5
Input
9 314159265 1 1 1 1 1 1 1 1 1
Output
314256789
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。