AtCoder Beginner Contest 087

更新日時:

AtCoder Beginner Contest 087

ソースコード

解法のメモ

A - Buying Sweets

$(X - A) \% B$ を出力する。

B - Coins

$K = \max(A, B, C)$ とする。 $O(K^3)$ でも十分間に合うが、 $O(K^2)$ の解法を書く。 $500$ 円玉を $i$ 枚、 $100$ 円玉を $j$ 枚使う際に、もし条件を充たすような $50$ 円玉の使い方があるとすれば、それは $(X - 500i - 100j)/50$ 枚ということになる。そこで $R = X - 500i - 100j$ とし、 $R \geq 0$ かつ $R \% 50 = 0$ かつ $R / 50 \leq C$ の時にカウンタを回せばよろしい。

ポイント

解説 PDF は $O(K^3)$ の解答だった。

その他

コメントする