問題は、非負整数 \(a, b\) が与えられて、

\[ \left \lbrace \begin{aligned} &x + y + z = a \\ &10 x + 5 y + z = b \end{aligned} \right . \]

を満たす非負整数 \(x, y, z\) があればそれを出力し、なければそれを報告してくださいという問題に帰着します。

まず \(x, y\) について解くと

\[ \left \lbrace \begin{aligned} x &= \frac 1 5 \left \lparen 4 z - 5 a +b \right \rparen \\ y &= \frac 1 5 \left \lparen -9z + 10 a -b \right \rparen \end{aligned} \right . \]

となりますから、このような非負整数 \(x, y\) が存在する非負整数 \(z\) の条件は

\[ \left \lbrace \begin{aligned} &z \equiv b \pmod 5 \\ &\frac { 5 a - b } 4 \le z \le \frac { 10 a - b } 9 \end{aligned} \right . \]

です。従って

\[ z _ 0 = \max \left \lparen 0, \left \lceil \frac { 5 a - b } 4 \right \rceil \right \rparen \]

とおくと解が存在するときには（\(z _ 0\) は解とは限りませんが）

\[ z = z _ 0 + \left \lparen \left \lparen b - z _0 \right \rparen \mathop{ \mathrm{rem}} 5 \right \rparen \]

（ただし整数 \(n\) に対して、\(n \mathop{\mathrm{rem}} 5\) は \(0 \le k \lt 5, n \equiv k \pmod 5\) を満たす唯一の整数 \(k\) のことです。）も解になります。

そこで、この \(z\) からもとの方程式により \(x, y\) を計算しましょう。すると \(0 \le x\) は必ず成り立ちますが、\(0 \le y\) は保証されておらず、解の存在と同値になります。従って \(0 \le y\) であればこの \(x, y, z\) を出力し、さもなくば解無しを報告すればよいです。

提出: https://atcoder.jp/contests/abc085/submissions/38871402

use num::Integer;
use proconio::input;

fn main() {
    input! { a: i64, b: i64 }
    let b = b / 1000;
    let z_min = (5 * a - b).max(0).div_ceil(&4);
    let z = z_min + (b - z_min).rem_euclid(5);
    let x = (4 * z + b) / 5 - a;
    let y = a - x - z;
    let (x, y, z) = if 0 <= y { (x, y, z) } else { (-1, -1, -1) };
    println!("{} {} {}", x, y, z);
}

オマケ解法

1000 円札を出す枚数を \(5\) で割った余りはすぐにわかりますから、先にそれを出すという方針もあります。

\(0 \le r \lt 5\) を満たす整数 \(a, b, r\) を用いて入っていたお札の総数がを \(a + r\)、合計金額が \(1000 ( 5 b + r)\) と表せば、解くべき方程式は

\[ \left \lbrace \begin{aligned} &x + y + 5z = a \\ &2x + y + z = b \end{aligned} \right . \]

となり、これは

\[ \left \lbrace \begin{aligned} &x = 4 z - a + b\\ &y = -9z + 2a - b \end{aligned} \right . \]

と同値ですから、\(5\) で割った余りを考えることなく解くことができて、少し簡単になります。ただ、最初に帰着する作業が入りますから、コード自体はこちらのほうがやや複雑になると思いますから、こちらをオマケ解法といたしました。

オマケ解法 2

5000 円札を 9 枚出す代わりに、1000 円札 5 枚と 10000 円札 4 枚を出しても、枚数も金額も変わりません。そこで、5000 円札は 9 枚未満としてよいです。5000 円札を出す枚数さえ決めてしまえば、あとは連立方程式を解くだけです。