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