[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;
}