ABC085C - Otoshidama Editorial by ngtkana
問題は、非負整数 \(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 円札を出す枚数さえ決めてしまえば、あとは連立方程式を解くだけです。
posted:
last update: