1. 


/* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #185 (Roman Numerals)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=121
*
* @author Dennis Wilfert
* @author Johann Studt
* @version 1.0, 05/12/2009
*
* Status : Accepted
* Runtime: 0.408
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;


public class Main {

public static void main(String[] args) throws IOException{
Main m = new Main();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

String line;
String summand1;
String summand2;
String sum;

int number1;
int number2;
int number3;

while(true)
{
line = reader.readLine();

if(line.equals("#"))
break;

summand1 = line.substring(0, line.indexOf("+"));
summand2 = line.substring(line.indexOf("+")+1,line.indexOf("="));
sum = line.substring(line.indexOf("=")+1);

number1 = m.convertDezimal(summand1);
number2 = m.convertDezimal(summand2);
number3 = m.convertDezimal(sum);


if(number1 + number2 == number3)
System.out.print("Correct ");
else
System.out.print("Incorrect ");

System.out.println(m.arabic(summand1, summand2, sum));
}

}

// Array der römischen Ziffern
char[] roman;
// Letztes zeichen
char lastchar;
// Länge des Arrays
int length;
/*
* Konvertieren von römischen Zahlen in dezimalzahlen
*/
public int convertDezimal(String str){

// Map mit Römischen Zahlen und dazugehörigen Dezimalzahlen
HashMap<Character, Integer> convert = new HashMap<Character, Integer>();
convert.put('I', 1);
convert.put('X', 10);
convert.put('C', 100);
convert.put('M', 1000);
convert.put('V', 5);
convert.put('L', 50);
convert.put('D', 500);

num = 0;
roman = str.toCharArray();
length = roman.length;

// Ersten von hinten gelesen als Summe speichern
int sum = convert.get(roman[length-1]);
lastchar = roman[length-1];

// Array von hinten nach vorne durchlaufen
for(int i = roman.length-2; i>=0; i--){

// Falls das letzte Zeichen gleich dem aktuellen ist
if(roman[i] == lastchar)
num+=2;

else{
num=0;
}
// Aktuelles Wert ist kleiner als der vorhergehende
if(convert.get(roman[i]) < convert.get(lastchar))
// Von der Summe abziehen
sum -= convert.get(roman[i]);

else
// Zur Summe addieren
sum += convert.get(roman[i]);

lastchar = roman[i];
}
// Ist der Wert gültig, dann die Summe an die Ausgabe hängen
return sum;
}
// Konvertierungstabelle
HashMap<Character, Integer> table;
// Alle vorkommenden chars
HashSet<Character> currentchars;
// Alle vorkommenden chars
char[] romanchars;
// Chars des 1. summanden
char[] s1array;
// Chars des 2. summanden
char[] s2array;
// Chars der summe
char[] sumarray;
// Anzahl der gültigen Ergebnisse
int erg;
// Character-Array zum zwischenspeichern
Character[] romancharacters;
// Werte die permutiert werden
int[] a = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
/*
* Prüfen, ob wenn für die Römischen Ziffern beliebige Werte zwischen 0 und 9 eingesetzt werden,
* ein gültiges Ergebnis heraus kommt
*/
public String arabic(String s1, String s2, String sum){

s1array = s1.toCharArray();
s2array = s2.toCharArray();
sumarray = sum.toCharArray();
// Die drei Arreys durchlaufen und jedes vorkommende Zeichen in currentchars speichern
currentchars = new HashSet<Character>();
for(char i: s1array)
currentchars.add(i);

for(char i: s2array)
currentchars.add(i);

for(char i: sumarray)
currentchars.add(i);

// currentchars in Characterarray umwandeln
romancharacters = currentchars.toArray(new Character[currentchars.size()]);

// CHaracterarray in chararray umwandeln
romanchars = new char[romancharacters.length];
for(char i=0; i< romancharacters.length; i++)
romanchars[i] = romancharacters[i];
erg = 0;
// k kombinationen
int k = romanchars.length;

table = new HashMap<Character, Integer>();

// k Kombinationen für k Elemente aus der Menge 10 durchlaufen
combinations(a, a.length, k);

if(erg==0)
return "impossible";
if(erg==1)
return "valid";

return "ambiguous";

}

/*
* Für alle verschiedenen Zahlenkombinationen Prüfen ob summand + summand = summe
*/
// Position im romanchars-Array
int num;
// Summe von s1
int s1sum;
// Summe von s2
int s2sum;
// Summe der Summe
int sumsum;
// Multiplikator
int mult;
public void combinations(int[] a, int n, int k) {
// Ist k == 0 kann für eine neue Zahlenkombination geprüft werden, ob die eine gültige Addition stattfinden kann
if (k == 0) {
num=0;
for (int i = n; i < a.length; i++){
table.put(romanchars[num], a[i]);
num++;
}


// Die erste Stelle der Summanden und des Ergebnis darf nicht 0 sein
if(table.get(s1array[0])==0)return;
if(table.get(s2array[0])==0)return;
if(table.get(sumarray[0])==0)return;
s1sum = 0;
mult = 1;
// Summe des ersten sumanden ausrechnen
for(int i = s1array.length-1; i >= 0; i--){

s1sum += table.get(s1array[i])*mult;
mult*=10;

}

s2sum = 0;
mult = 1;
// Summe des zweiten Sumanden ausrechnen
for(int i = s2array.length-1; i >= 0; i--){

s2sum += table.get(s2array[i])*mult;
mult*=10;

}

sumsum = 0;
mult = 1;
// Summe der Summe ausrechnen
for(int i = sumarray.length-1; i >= 0; i--){

sumsum += table.get(sumarray[i])*mult;
mult*=10;

}
// Wenn summand + summand = summe, dann erg um 1 erhöhen
if(s1sum + s2sum == sumsum)
erg++;

return;
}
// Solange i<n Werte vertauschen und die Funktion combinations mit reduziertem n und k wieder aufrufen
for (int i = 0; i < n; i++) {
swap(a, i, n-1);
combinations(a, n-1, k-1);
swap(a, i, n-1);
}
}
/*
* Werte im Array an den Positionen i und j vertauschen
*/
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}