#AT1175. C - Otoshidama
C - Otoshidama
当前没有测试数据。
C - Otoshidama
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:
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.
9 45000
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.
20 196000
-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.
1000 1234000
14 27 959
There are also many other possibilities.
2000 20000000
2000 0 0