問題一覧 > 通常問題

No.1630 Sorting Integers (Greater than K)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : とりゐとりゐ / テスター : re_re0101re_re0101 karinohitokarinohito
2 ProblemId : 6758 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-30 03:03:02

問題文

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