We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #89: Roman numerals

Project Euler #89: Roman numerals

The values of Roman Numeral symbols in decimal are the following: 

I - 1  
V - 5  
X - 10  
L - 50  
C - 100  
D - 500  
M - 1000

In general, a roman number is written in descending order of symbols which are to be added.
For example, is written as as and are to be added and is subtracted from . One does not write 14 as IVX or 15 as VX. This is because, appearance of a symbol with lesser value before another symbol implies subtraction.

Rules for subtraction:

  1. I can only be subtracted from V and X.
  2. X can only be subtracted from L and C.
  3. C can only be subtracted from D and M.
  4. V, L, D and M can't be subtracted from any symbol.
  5. At most one symbol can be subtracted from another symbol.

For example, would be written as CMXCIX and not IM.

One last rule to be kept in mind while writing Roman Numerals is that except M, no numeral appears more than 3 times in a row and none of V, L, D appear even twice in a row. Hence 9 is IX and not VIIII.

In this task, you'll be given symbols in descending order which represent a number. You have to output a valid roman numeral representation of that number by following the above rules.

For example, the following represent all of the legitimate ways of writing the number sixteen:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

The last example being considered the most efficient, as it uses the least number of numerals.

Input Format

First line contains a single integer denoting the number of test-cases.
lines follow, each contains a string representing a number.

Output Format

Output lines, line should contain the correct roman number representation of the string in the input.

Constraints:

Sample Input

5
IIIII
VVVVVVVVV
MMMMMMMMMMMMMIIII
LLLXXXXX
CCXX

Sample Output

V
XLV
MMMMMMMMMMMMMIV
CC
CCXX

Explanation

  1. More than 3 symbols can't appear in a row.
  2. V can't be subtracted from anything.
  3. More than 3 M can appear in a row.
  4. Converting all X to L makes LLLL which is not valid since V, L, D can not appear more than once in a row.
  5. This is an example of a correct representation.