## 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);
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;
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;
}
```