問題一覧 > 通常問題

No.115 遠足のおやつ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 253
作問者 : kroton
16 ProblemId : 205 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:12

問題文

直樹くんは遠足のおやつを買いに駄菓子屋さんに来ました。
駄菓子屋さんは 1,2,3…N 円の N 種類のお菓子を売っています。

直樹くんが買えるおかしは合計で D 円までで、買える個数は K 個までです。
いっぱいおかしが食べたい直樹くんは次のルールを追加しました。

  • お金があまったらもったいないので、合計が D 円ぴったりになるようにおかしを買う
  • いっぱい食べたいので K 個おかしを買う
  • 種類もいっぱい食べたいので、ある金額のおかしは買うなら 1 個までにする

このルールを満たすようなおかしの買い方で辞書順最小になるものを答えてください。
もしそのようなおかしの買い方がないなら −1 を出力してください。

辞書順最小についてはサンプルを参照してください。

入力

N D K

入力はすべて整数で与えられる

  • 1≤N≤100
  • 1≤D≤1000
  • 1≤K≤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もしくは右上の雲マークをクリックしてアカウントを作成してください。