TakahiroNakamori

TakahiroNakamori

中森崇博(ナカモリタカヒロ)

12 /
19
2021
 

Send More Money

問題

D – Send More Money
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

int main() {
  string S1, S2, S3;
  cin >> S1 >> S2 >> S3;

  map<char, int> mp;
  int cnt = 1;

  int n1 = S1.size();
  vector<int> s1(n1);
  rep(i, n1) {
    if(mp[S1[i]] == 0) {
      mp[S1[i]] = cnt;
      cnt++;
    }
    s1[i] = mp[S1[i]];
  }

  int n2 = S2.size();
  vector<int> s2(n2);
  rep(i, n2) {
    if(mp[S2[i]] == 0) {
      mp[S2[i]] = cnt;
      cnt++;
    }
    s2[i] = mp[S2[i]];
  }

  int n3 = S3.size();
  vector<int> s3(n3);
  rep(i, n3) {
    if(mp[S3[i]] == 0) {
      mp[S3[i]] = cnt;
      cnt++;
    }
    s3[i] = mp[S3[i]];
  }

  rep(i, n1) { s1[i]--; }
  rep(i, n2) { s2[i]--; }
  rep(i, n3) { s3[i]--; }
  cnt--;

  if(10 < cnt) {
    cout << "UNSOLVABLE" << endl;
    return 0;
  }

  vector<ll> v;
  rep(i, 10) { v.push_back(i); }

  do {
    ll ans1 = 0;
    ll ans2 = 0;
    ll ans3 = 0;

    if(v[s1[0]] == 0 || v[s2[0]] == 0 || v[s3[0]] == 0) {
      continue;
    }

    rep(i, n1) {
      if(i == 0) {
        ans1 = v[s1[i]];
      } else {
        ans1 = ans1 * 10 + v[s1[i]];
      }
    }

    rep(i, n2) {
      if(i == 0) {
        ans2 = v[s2[i]];
      } else {
        ans2 = ans2 * 10 + v[s2[i]];
      }
    }

    rep(i, n3) {
      if(i == 0) {
        ans3 = v[s3[i]];
      } else {
        ans3 = ans3 * 10 + v[s3[i]];
      }
    }

    if(ans1 + ans2 == ans3) {
      cout << ans1 << endl;
      cout << ans2 << endl;
      cout << ans3 << endl;
      return 0;
    }
  } while(next_permutation(v.begin(), v.end()));

  cout << "UNSOLVABLE" << endl;
  return 0;
}