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");
}
}
}