問題の概要

　お年玉を $N$ 枚 $(1 \leq N \leq 2000)$ のお札で合計 $Y$ 円 $(1000 \leq Y \leq 2 \times 10^{7})$ いただいた。このとき、10000円札・5000円札・1000円札の枚数を求める。

　但し、複数の可能性がある場合はそのうちの1組を出力する。また、お札の組み合わせが存在しない場合は-1 -1 -1と出力。

解答例

	10000円札	5000円札	1000円札
枚数	$X_{10}$	$X_{5}$	$X_{1}$

　式(1)より、1000円札の枚数 $X_{1}$ を計算によって求めることができる。したがって、3種類のお札を全探索した場合の計算量 $O(N^{3})$ から $O(N^{2})$ へ削減できる。

　また、AtCoder上の環境では、平均実行時間7 msとなった。

　式(1)及び(2)より、10000万円札の枚数 $X_{10}$ を固定すると、二元一次連立方程式となる。したがって、3種類のお札を全探索した場合の計算量 $O(N^{3})$ から $O(N)$ へ削減できる。

　　また、AtCoder上の環境では、平均実行時間1 msとなった。