[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\) となります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int A, B, C; int ans = 100000; void solve(int v, int a, int b) { int r = a + 10 * b - v; int k = r / 10 + r % 10; if (A + B - (a + b) + k == C) { ans = min(ans, v); } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> A >> B >> C; int v = A + 10 * B; for (int a = 0; a <= A; a++) { for (int b = 0; b <= B; b++) { for (int v = 1; v <= a + 10 * b; v++) { solve(v, a, b); } } } if (ans == 100000) { cout << "Impossible\n"; } else { cout << ans << "\n"; } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません