로마 숫자

초기 로마인들이 사용한 수 표기법은 단순하지만 번거로웠다. 중요한 수를 나타내는 여러 글자를 정해 두고, 이 글자들을 왼쪽에서 오른쪽으로 값이 단조 감소하도록 늘어놓아 다른 수를 표현했다. 사용한 글자와 그 값은 아래 표와 같다.

따라서 1993은 MDCCCCLXXXXIII로 적었다. 이후 이 방식은 부분적으로 자리값을 사용하는 방식으로 대체되었다. 값이 감소해야 한다는 규칙이 깨지면, 바로 앞의 (더 작은) 값을 음수로 간주하여 뒤따르는 (제자리를 벗어난) 더 큰 값에서 빼는 것이다. 이 방식에서 1993은 보통 MCMXCIII로 적었다. 어떤 글자가 어떤 글자 앞에 올 수 있는지에 대해서는 여전히 논란이 있지만, 이 문제에서는 다음 제약을 가정한다.

• 왼쪽 열의 글자는 연속으로 세 번을 넘겨 나타날 수 없으며, 그 글자가 추가로 나타나는 경우는 많아야 한 번뿐이다.
• 오른쪽 열의 글자는 한 번을 넘겨 나타날 수 없다.
• 어떤 글자가 한 번 "음수" 위치에 쓰이면, 그 바로 다음 글자를 제외한 이후의 모든 글자는 그 글자보다 클 수 없다.

따라서 1993을 MXMIII로, 294를 CCXCIV로 적을 수 있다. 그러나 54를 ILV로, 99를 LIL로 적을 수는 없다. 참고로 299는 CCXCIX 또는 CCIC로 적을 수 있다.

로마 숫자로 된 합은 그대로 해석할 수도 있고, 서로 다른 각 글자가 하나의 십진 숫자를 나타내는 아라비아(십진) 합의 부호화로 해석할 수도 있다. 예를 들어 V+V=X는 $V \in \{1,2,3,4\}$이고 $X = 2V$인 아라비아 합의 부호화로 읽을 수 있으므로 모호하다(ambiguous). 마찬가지로 X+X=XX는 올바른 로마 합이지만 (금지된 자명한 해 X = 0을 제외하면) 아라비아 부호화로는 불가능하다(impossible). 그리고 XX+XX=MXC는 올바르지 않은 로마 합이지만 M = 1, X = 9, C = 8로 성립하는 유효한(valid) 부호화이다.

로마 숫자로 쓰인 합들을 읽어, 각 합이 로마 합으로서 올바른지, 그리고 아라비아 부호화로서 불가능한지·모호한지·유효한지를 판정하는 프로그램을 작성하라. 0은 단독으로도, 맨 앞자리에도 나타나지 않는다고 가정하며, 서로 다른 두 로마 글자는 같은 아라비아 숫자에 대응하지 않는다.

입력은 여러 줄로 이루어진다. 각 줄은 하나의 로마 합처럼 보이는 식으로, 유효한 로마 수, 더하기 기호(+), 또 다른 유효한 로마 수, 등호(=), 그리고 세 번째 유효한 로마 수로 구성된다. 어떤 로마 수도 9글자를 넘지 않는다. 입력은 문자 #만 있는 줄로 끝난다.

입력의 각 줄마다 정확히 두 단어를 공백 하나로 구분하여 한 줄에 출력한다. 첫 번째 단어는 로마 합이 올바르면 Correct, 그렇지 않으면 Incorrect이다. 두 번째 단어는 아라비아 부호화에 따라 impossible, ambiguous, valid 중 하나이다.