No.115 Snacks for the School Excursion
タグ : / 解いたユーザー数 270
作問者 :
Problem Statement
Naoki has come to a candy shop to buy snacks for a school excursion.
The candy shop sells \(N\) kinds of snacks, priced at \(1, 2, 3 \dots N\) yen.
Naoki can buy snacks totaling up to \(D\) yen, and he can buy up to \(K\) snacks.
Naoki, who wants to eat a lot of snacks, added the following rules.
- Leaving money over would be a waste, so he buys snacks so that the total is exactly \(D\) yen
- He wants to eat a lot, so he buys \(K\) snacks
- He also wants to eat many kinds, so he buys at most \(1\) snack of any given price
Find the lexicographically smallest way of buying snacks that satisfies these rules.
If there is no such way of buying snacks, output \(-1\).
For the meaning of lexicographically smallest, refer to the samples.
Input
\(N\) \(D\) \(K\)
All inputs are given as integers
- \(1 \leq N \leq 100\)
- \(1 \leq D \leq 1000\)
- \(1 \leq K \leq 10\)
Output
Output the lexicographically smallest way of buying snacks that satisfies the rules, on one line, separated by spaces.
However, if there is no such way of buying snacks, output -1.
Sample
Sample 1
Input
10 9 3
Output
1 2 6
The combinations of snacks that satisfy the rules are the following
- (\(1\) yen, \(2\) yen, \(6\) yen)
- (\(1\) yen, \(3\) yen, \(5\) yen)
- (\(2\) yen, \(3\) yen, \(4\) yen)
3 in total, and among these, the lexicographically smallest combination (\(1\) yen, \(2\) yen, \(6\) yen) is the answer.
Sample 2
Input
10 9 4
Output
-1
Unfortunately, Naoki could not buy any snacks...
Sample 3
Input
30 40 4
Output
1 2 7 30
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。