Source file: | numeral.{c, cpp,
java} |

Input file: | numeral.in |

Rule Δ: Add together the values for each symbol that is either the rightmost or has a symbol of no greater value directly to its right. Subtract the values of all the other symbols.

For example: MMCDLXIX = 1000 + 1000 - 100 + 500 + 50 + 10 - 1 + 10 = 2469.

Further rules are needed to uniquely specify a Roman numeral corresponding to a positive integer less than 4000:

- The numeral has as few characters as possible. (IV not IIII)
- All the symbols that make positive contributions form a non-increasing subsequence. (XIV, not VIX)
- All subtracted symbols appear as far to the right as possible. (MMCDLXIX not MCMDLIXX)
- Subtracted symbols are always for a power of 10, and always appear directly to the left of a symbol 5 or 10 times as large that is added. No subtracted symbol can appear more than once in a numeral.

4'. With a
choice of numeral representations of the same
length, use one with the fewest subtracted symbols.

Finally, replace the Roman numeral symbols to make a system that is more regular and allows larger numbers: Assign the English letter symbols a, A, b, B, c, C, …, y, Y, z, and Z to values 1, 5, 10, 5(10), 10

With the new symbols a-Z, the original formation rules 1-3, the alternate rule 4', and the evaluation rule Δ, numerals can be created, called A to Z numerals. Examples: ad = -1 + 1000 = 999; aAc = -1 - 5 + 100 = 94. Note that for this problem, an A to Z Numeral cannot include the same uppercase literal twice.

**Input: **The
input starts with a sequence
of one or more positive integers less than (7)10^{17},
one per line.
The end of the input is indicated by a line containing only 0.

**Output: **For
each positive integer in the
input, output a line containing only an A to Z numeral representing the
integer.

Do not choose a solution method whose time is exponential in the number of digits!

Example input: |
Example output: |

999 198 98 297 94 666666666666666666 0 |
ad acac Acaaa ccAcaa aAc RrQqPpOoNnMmLlKkJjIiHhGgFfEeDdCcBbAa |

*Last modified on October 24, 2009 at 9:40 PM.*