A - Rzymianie

Pierwotny rzymski system zapisywania liczb był prosty, ale dość niewygodny. Dla oznaczenia ważnych liczb używano różnych liter, powiązanych w celu przedstawienia innych liczb, przy czym wartości kolejnych składowych spadały od lewej do prawej. Wspomniane litery, używane przez Rzymian oraz liczby, które oznaczały przedstawiono poniżej:

I – 1 V – 5

X – 10 L – 50

C – 100 D – 500

M – 1000

I tak, na przykład, rok 1993 zapisywano jako MDCCCCLXXXXIII. Ten system został zastąpiony częściowym systemem pozycyjnym, w którym zasada opadających wartości liczb została złamana, a poprzedzająca wartość była traktowana jako „negatywna” i odejmowana od wyższej (nie znajdującej się na swojej pozycji) wartości. W tym systemie rok 1993 był zazwyczaj zapisywany jako MCMXCIII. Trwają ciągle dyskusje, które litery powinny poprzedzać inne, ale dla naszych celów wprowadzono następujące ograniczenia:

· litera z lewej kolumny nie może pojawić się więcej niż trzy razy w linii i nie może wystąpić nigdzie indziej więcej niż raz.

· litera z prawej kolumny nie może się nigdzie pojawić więcej niż raz.

· jeśli litera zostanie użyta na pozycji „negatywnej”, wszystkie kolejne litery (poza bezpośrednio następującą) nie mogą być większe od tej pierwszej.

Możemy więc zapisać 1993 jako MXMIII albo 294 jako CCXCIV; ale nie możemy 54 jako ILV ani 99 jako LIL. Zauważ, że 299 można zapisać jako CCXCIX albo CCIC.

Mając więc sumę rzymską, możemy ją traktować jako właśnie taką, albo jako zakodowaną sumę arabską. I tak, V+V = X można rozumieć jako dwuznaczne zakodowanie arabskiej sumy, gdzie V $\in$\{1,2,3,4\} i X=2*V. Podobnie, X+X=XX może być interpretowane jako prawidłowa suma rzymska, niewyrażalna w systemie arabskim. (z wyjątkiem trywialnego przypadku, gdy X=0, ale to też nie jest prawidłowe, bo nie zapisujemy w systemie arabskim liczb 00), a np. XX+XX=MXC jest nieprawidłową sumę rzymską, ale możliwą do odkodowania sumą arabską (M = 1, X = 9, a C = 8).

Zadanie:

Napisz program, który dla danego wyrażenia na wejściu stwierdzi, czy jest on prawidłową sumą rzymską, a później sprawdzi, czy można odkodować odpowiednie litery na cyfry tak, aby podane wyrażenie było prawidłową sumą arabską (zakładamy, że liczba arabska dodatnia nigdy nie zaczyna się na 0, oraz, że dwóm różnym literkom nie odpowiadają te same cyfry arabskie)

Wejście:

Wejście zawiera serię linii, każda zawierającą prawidłową lub nieprawidłową sumę rzymską zapisaną w postaci liczby rzymskiej, znaku dodawania (+), drugiej liczby rzymskiej, znaku równości (+) i kolejnej liczby rzymskiej będącej potencjalnym wynikiem dodania pierwszych dwóch. Każda liczba rzymska składa się z nie więcej niż 9 liter. Ostatnia wejścia zawiera znak # (tylko)

Wyjście:

Wyjście zawiera serię linii, z których każda odpowiada odpowiedniej linii wejścia. Pierwsze słowo w linii to Correct lub Incorrect – zależy ono, czy rzymska suma jest prawidłowa, czy nie. Drugie słowo, po spacji, jest jednym ze słów impossible, ambiguous, valid i oznaczają odpowiednio niemożliwy, niejednoznaczny i prawidłowy, a jego wartość zależy od tego, jak zachowuje się suma arabska.

Przykład:

Wejście:

V+V=X

X+X=XX

XX+XX=MXC

Wyjście:

Correct ambiguous

Correct impossible

Incorrect valid