/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。
制約
- 1 ≤ N ≤ 2000
- 1000 ≤ Y ≤ 2 × 10^7
- N は整数である。
- Y は 1000 の倍数である。
入力
入力は以下の形式で標準入力から与えられる。
N Y
出力
N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。
N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。
入力例 1
9 45000
出力例 1
4 0 5
お年玉袋に 10000 円札 4 枚と 1000 円札 5 枚が入っていれば、合計枚数が 9 枚、合計金額が 45000 円になります。5000 円札 9 枚という可能性も考えられるため、0 9 0 も正しい出力です。
入力例 2
20 196000
出力例 2
-1 -1 -1
合計枚数が 20 枚の場合、すべてが 10000 円札であれば合計金額は 200000 円になり、そうでなければ 195000 円以下になるため、196000 円という合計金額はありえません。
入力例 3
1000 1234000
出力例 3
14 27 959
この他にも多くの候補があります。
入力例 4
2000 20000000
出力例 4
2000 0 0
Score : 300 points
Problem Statement
The commonly used bills in Japan are 10000-yen, 5000-yen and 1000-yen bills. Below, the word "bill" refers to only these.
According to Aohashi, he received an otoshidama (New Year money gift) envelope from his grandfather that contained N bills for a total of Y yen, but he may be lying. Determine whether such a situation is possible, and if it is, find a possible set of bills contained in the envelope. Assume that his grandfather is rich enough, and the envelope was large enough.
Constraints
- 1 ≤ N ≤ 2000
- 1000 ≤ Y ≤ 2 × 10^7
- N is an integer.
- Y is a multiple of 1000.
Input
Input is given from Standard Input in the following format:
N Y
Output
If the total value of N bills cannot be Y yen, print -1 -1 -1.
If the total value of N bills can be Y yen, let one such set of bills be "x 10000-yen bills, y 5000-yen bills and z 1000-yen bills", and print x, y, z with spaces in between. If there are multiple possibilities, any of them may be printed.
Sample Input 1
9 45000
Sample Output 1
4 0 5
If the envelope contained 4 10000-yen bills and 5 1000-yen bills, he had 9 bills and 45000 yen in total. It is also possible that the envelope contained 9 5000-yen bills, so the output 0 9 0 is also correct.
Sample Input 2
20 196000
Sample Output 2
-1 -1 -1
When the envelope contained 20 bills in total, the total value would be 200000 yen if all the bills were 10000-yen bills, and would be at most 195000 yen otherwise, so it would never be 196000 yen.
Sample Input 3
1000 1234000
Sample Output 3
14 27 959
There are also many other possibilities.
Sample Input 4
2000 20000000
Sample Output 4
2000 0 0