No.1630 Sorting Integers (Greater than K)
タグ : / 解いたユーザー数 94
作問者 :
とりゐ
/ テスター :
re_re0101
karinohito
問題文
$1$ 桁の正整数が $N$ 個あります．このうち $i$ は $c_i$ 個です $(1\leq i\leq9)$．これら $N$ 個の整数を並べ替え，それを $N$ 桁の $10$ 進法の整数 $M$ とみなしたとき，$K$ より大きい $M$ のうち最小のものを求めてください．
入力
$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$
- 入力は全て整数である
出力
$K$ より大きい $M$ が存在する場合はその最小値を，存在しない場合は -1 を出力してください．
サンプル
サンプル1
入力
3 200 1 1 1 0 0 0 0 0 0
出力
213
$1,2,3$ が $1$ つずつあり，$M$ として考えられるものは $123,132,213,231,312,321$ があります．$200$ より大きい最小の $M$ は $213$ です．
サンプル2
入力
3 213 1 1 1 0 0 0 0 0 0
出力
231
$1,2,3$ が $1$ つずつあり，$M$ として考えられるものは $123,132,213,231,312,321$ があります．$213$ より大きい最小の $M$ は $231$ です．
サンプル3
入力
3 400 1 1 1 0 0 0 0 0 0
出力
-1
$1,2,3$ が $1$ つずつあり，$M$ として考えられるものは $123,132,213,231,312,321$ があります．$400$ より大きい $M$ は存在しません．．
サンプル4
入力
3 1 0 3 0 0 0 0 0 0 0
出力
222
$2$ が $3$ つあり，$M$ として考えられるものは $222$ のみです．$1$ より大きい最小の $M$ は $222$ です．
サンプル5
入力
9 314159265 1 1 1 1 1 1 1 1 1
出力
314256789
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。