解き方だけ書きます。
一万円札、五千円札、千円札の枚数をそれぞれ x, y, z とすると、
x + y + z = c ... (式1) 10000x + 5000y + 1000z = a ...(式2)
これらの式が導かれます。
c はお札の総枚数、a は合計額です。
この 2 つは定数で入力データとして与えられます。
お札の総枚数と合計額が与えられるので、これを満たす x, y, z つまり
一万円札、五千円札、千円札のそれぞれの枚数を求めなさい。
(複数の解がある場合はすべてを網羅する必要無し。)
という問題です。
さて、(式1)を変形して
y = c - x - z
と y を表す事が出来るので、 (式2)にこれを適用すると、
10000x + 5000(c - x - z) + 1000z = a
となり、この式を整理して z で表すと、
z = (5000x + 5000c - a) / 4000 ...(式3)
となります。
同様に、(式1)を変形して
z = c - x - y
と z を表す事が出来るので、(式2)にこれを適用すると、
10000x + 5000y + 1000(c - x - y) = a
となり、この式を整理して y で表すと、
y = (a - 9000x - 1000c) / 4000 ..(式4)
となります。
まとめると、
z = (5000x + 5000c - a) / 4000 ...(式3) y = (a - 9000x - 1000c) / 4000 ..(式4)
となります。
ここで先にも書いた通り、a と c は合計額と総枚数で定数としてプログラムに与えられるので、
つまり y と z は x の値が決まれば求められる事がわかります。
あとは x の範囲をどうすれば良いかを考えます。
x は一万円札の枚数ですから、
x の範囲は 0 以上で、かつ、 10000 * x が a (総合計) 以下
である事がわかります。
具体的に a (総合計) が 55,000円だったら、x の範囲は、
0 <= x <= 5
と決まります。
x は 0 から始めて 1 ずつ増やしていき、この範囲内にあるときに、
x から y と z を求めて、
10000 * x + 5000 * y + 1000 * z = a (合計額)
になるのであれば x と y と z が解です。
x が総合計の範囲を超えてしまったら「解なし」です。
x だけを走査すれば良いので一重ループで実装できます。
注意しなければならないのは、 x の値によっては y と z のいずれか、あるいは両方が
マイナス値になる事があります。お札の枚数がマイナスになる事はありえないので
解から除外しなければいけません。
この問題は、何も考えず多重ループにしてしまうと制限時間オーバーになり正答できません。
計算時間をいかにして減らす工夫が出来るか、が試されます。
