[yukicoder] No. 825 賢いお買い物

問題

方針

全探索

硬貨の組み合わせ方は、\( (A + 1)(B + 1) \) 通りあります。\( 1G \) と \(10G\) 硬貨の使用枚数をそれぞれ、\( a, b \) とします。ただし、\( 0 \leq a \leq A \) かつ \( 0 \leq b \leq B\) を満たします。ただし、\( a \neq 0 \wedge b \neq 0 \) です。

この硬貨を用いて買うことができる商品の値段を \( v \) とすると、\( 1 \leq v \leq a + 10b \) となります。これらの条件下で全探索を行います。

おつりの硬貨の枚数

通常の硬貨の支払いと異なり、冗長な支払い方でも大丈夫なように考える必要があります。\( 1G \) と \(10G\) 硬貨の使用枚数をそれぞれ、\( a, b \) としたとき、\( v \) 円の商品を買った時のおつりの硬貨の枚数は、\( k = a + 10b – v\) 円を最小の硬貨で表現したときの枚数です。このときのおつりの硬貨は、

\[ \lfloor \dfrac{k}{10} \rfloor + k \bmod 10\]

となります。よって、全体の硬貨枚数は、\( A + B – (a + b) + k\) となります。

コード