問題一覧 > 通常問題

No.1630 Sorting Integers (Greater than K)

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

問題文

1 桁の正整数が N 個あります．このうち i は ci 個です (1≤i≤9)．これら N 個の整数を並べ替え，それを N 桁の 10 進法の整数 M とみなしたとき，K より大きい M のうち最小のものを求めてください．

入力

N K
c1 c2 c3 c4 c5 c6 c7 c8 c9

  • 1≤N≤500000
  • 1≤K≤10500001
  • ci≥0
  • ∑i=19ci=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もしくは右上の雲マークをクリックしてアカウントを作成してください。