No.115 遠足のおやつ
kroton問題文最終更新日: 2015-11-14 17:47:12
問題文
直樹くんは遠足のおやつを買いに駄菓子屋さんに来ました。
駄菓子屋さんは \(1, 2, 3 \dots N\) 円の \(N\) 種類のお菓子を売っています。
直樹くんが買えるおかしは合計で \(D\) 円までで、買える個数は \(K\) 個までです。
いっぱいおかしが食べたい直樹くんは次のルールを追加しました。
- お金があまったらもったいないので、合計が \(D\) 円ぴったりになるようにおかしを買う
- いっぱい食べたいので \(K\) 個おかしを買う
- 種類もいっぱい食べたいので、ある金額のおかしは買うなら \(1\) 個までにする
このルールを満たすようなおかしの買い方で辞書順最小になるものを答えてください。
もしそのようなおかしの買い方がないなら \(-1\) を出力してください。
辞書順最小についてはサンプルを参照してください。
入力
\(N\) \(D\) \(K\)
入力はすべて整数で与えられる
- \(1 \leq N \leq 100\)
- \(1 \leq D \leq 1000\)
- \(1 \leq K \leq 10\)
出力
ルールを満たすようなおかしの買い方で辞書順最小になるものをスペース区切りで一行に出力してください。
ただしそのようなおかしの買い方がない場合は-1を出力してください。
サンプル
サンプル1
入力
10 9 3
出力
1 2 6
ルールを満たすおかしの組み合わせは
- (\(1\)円, \(2\)円, \(6\)円)
- (\(1\)円, \(3\)円, \(5\)円)
- (\(2\)円, \(3\)円, \(4\)円)
の3つがありますが、このうち辞書順が最小になる (\(1\)円, \(2\)円, \(6\)円) の組み合わせが答えになります。
サンプル2
入力
10 9 4
出力
-1
残念ながら直樹くんはおかしを買うことができませんでした・・・
サンプル3
入力
30 40 4
出力
1 2 7 30
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。