2013年8月21日

UVa 185 - Roman Numerals

#include <cstdio>
#include <string>
#include <vector>
#include <map>
#define PB push_back
using namespace std;

int solutionNumber;
char a[99], b[99], c[99];

void solve(int now, vector<char> & all, int * value, bool * used, bool * head) {
  if (solutionNumber > 1) {
    return;
  }
  if (now == all.size()) {
    int n1 = 0, n2 = 0, n3 = 0;
    for (int i = 0; a[i]; i++) {
      n1 = n1 * 10 + value[a[i]];
    }
    for (int i = 0; b[i]; i++) {
      n2 = n2 * 10 + value[b[i]];
    }
    for (int i = 0; c[i]; i++) {
      n3 = n3 * 10 + value[c[i]];
    }
    if (n1 + n2 == n3) {
      solutionNumber++;
    }
    return;
  }
  for (int d = 0 + head[all[now]]; d < 10 && solutionNumber <= 1; d++) {
    if (!used[d]) {
      value[all[now]] = d;
      used[d] = true;
      solve(now + 1, all, value, used, head);
      used[d] = false;
    }
  }
}

const int S1 = 13;
const int v1[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
const string s1[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
const int S2 = 16;
const int v2[] = {1, 4, 5, 9, 10, 40, 50, 90, 99, 100, 400, 500, 900, 990, 999, 1000};
const string s2[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "IC", "C", "CD", "D", "CM", "XM", "IM", "M"};

int main() {
  map<string, int> dic;
  for (int n = 1; n < 4000; n++) {
    int num = n;
    string roman;
    for (int i = S1 - 1; i >= 0 && num; i--) {
      while (num >= v1[i]) {
        roman += s1[i];
        num -= v1[i];
      }
    }
    dic[roman] = n;
  }
  for (int n = 1; n < 4000; n++) {
    int num = n;
    string roman;
    for (int i = S2 - 1; i >= 0 && num; i--) {
      while (num >= v2[i]) {
        roman += s2[i];
        num -= v2[i];
      }
    }
    dic[roman] = n;
  }
  char s[999];
  while (gets(s) && s[0] != '#') {
    bool ch[26] = {};
    for (int i = 0; s[i]; i++) {
      if (s[i] == '+' || s[i] == '=') {
        s[i] = ' ';
      } else {
        ch[s[i] - 'A'] = true;
      }
    }
    sscanf(s, "%s%s%s", a, b, c);
    bool head[128] = {};
    head[a[0]] = true;
    head[b[0]] = true;
    head[c[0]] = true;
    vector<char> all;
    for (int i = 0; i < 26; i++) {
      if (ch[i]) {
        all.PB(i + 'A');
      }
    }
    int value[128] = {};
    bool used[10] = {};
    solutionNumber = 0;
    solve(0, all, value, used, head);
    printf("%s ", dic[a] + dic[b] == dic[c] ? "Correct" : "Incorrect");
    switch (solutionNumber) {
      case 0:
        puts("impossible");
        break;
      case 1:
        puts("valid");
        break;
      default:
        puts("ambiguous");
        break;
    }
  }
  return 0;
}

沒有留言:

張貼留言