http://acm.pku.edu.cn/JudgeOnline/problem?id=1213
Код:
#include <stdio.h> #include <string.h> #include <limits.h> typedef unsigned int uint; uint Romanchartoint(char c) { switch (c) { case 'I': return 1; case 'V': return 5; case 'X': return 10; case 'L': return 50; case 'C': return 100; case 'D': return 500; case 'M': return 1000; case '\0':return 0; default: return c / 0; } } uint Romantoint(char s[]) { int i, len; uint value = 0; len = strlen(s); for (i = 0; i < len; i++) { if (Romanchartoint(s[i+1]) > Romanchartoint(s[i])) { value -= Romanchartoint(s[i]); } else { value += Romanchartoint(s[i]); } } return value; } uint RomanasArabic(char s[], int I, int V, int X, int L, int C, int D, int M) { int i, len; uint value = 0; len = strlen(s); for (i = 0; i < len; i++) { value *= 10; switch (s[i]) { case 'I': value += I; break; case 'V': value += V; break; case 'X': value += X; break; case 'L': value += L; break; case 'C': value += C; break; case 'D': value += D; break; case 'M': value += M; break; } if (value == 0) return UINT_MAX; } return value; } int exist(int values[], int using[], int depth, int t) { int i; for (i = 0; i < depth; i++) { if (values[i] == t && using[i]) return 1; } return 0; } int recursive(char a1[], char a2[], char b[], int using[], int depth, int values[], int *found) { int i; uint a1v, a2v, bv; if (depth == 7) { a1v = RomanasArabic(a1, values[0], values[1], values[2], values[3], values[4], values[5], values[6]); a2v = RomanasArabic(a2, values[0], values[1], values[2], values[3], values[4], values[5], values[6]); bv = RomanasArabic(b, values[0], values[1], values[2], values[3], values[4], values[5], values[6]); if (a1v + a2v == bv && a1v != UINT_MAX && a2v != UINT_MAX && bv != UINT_MAX) { (*found)++; } return 0; } if (!using[depth]) { if (recursive(a1, a2, b, using, depth+1, values, found)) return 1; } else { for (i = 0; i < 10; i++) { if (!exist(values, using, depth, i)) { values[depth] = i; if (recursive(a1, a2, b, using, depth+1, values, found)) return 1; } } } return 0; } int main() { char s[1024]; char *p; char a1[16], a2[16], b[32]; uint l, r; int using[8]; int i, len; int values[8]; int found; while (1) { gets(s); if (strcmp(s, "#") == 0) break; p = strtok(s, " +"); strcpy(a1, p); p = strtok(NULL, " ="); strcpy(a2, p); p = strtok(NULL, " " ); strcpy(b, p); l = Romantoint(a1) + Romantoint(a2); r = Romantoint(b); if (l == r) { printf("Correct "); } else { printf("Incorrect "); } for (i = 0; i < 7; i++) { using[i] = 0; } len = strlen(a1); for (i = 0; i < len; i++) { if (a1[i] == 'I') using[0] = 1; if (a1[i] == 'V') using[1] = 1; if (a1[i] == 'X') using[2] = 1; if (a1[i] == 'L') using[3] = 1; if (a1[i] == 'C') using[4] = 1; if (a1[i] == 'D') using[5] = 1; if (a1[i] == 'M') using[6] = 1; } len = strlen(a2); for (i = 0; i < len; i++) { if (a2[i] == 'I') using[0] = 1; if (a2[i] == 'V') using[1] = 1; if (a2[i] == 'X') using[2] = 1; if (a2[i] == 'L') using[3] = 1; if (a2[i] == 'C') using[4] = 1; if (a2[i] == 'D') using[5] = 1; if (a2[i] == 'M') using[6] = 1; } len = strlen(b); for (i = 0; i < len; i++) { if (b[i] == 'I') using[0] = 1; if (b[i] == 'V') using[1] = 1; if (b[i] == 'X') using[2] = 1; if (b[i] == 'L') using[3] = 1; if (b[i] == 'C') using[4] = 1; if (b[i] == 'D') using[5] = 1; if (b[i] == 'M') using[6] = 1; } found = 0; recursive(a1, a2, b, using, 0, values, &found); if (found == 0) { printf("impossible\n"); } if (found == 1) { printf("valid\n"); } if (found > 1) { printf("ambiguous\n"); } } }