SPOJ.com - Problem PROG0420

PROG0420 - Roman numerals

In ancient Rome a numeric system was used for the representation of integers, that employed combinations of letters from the Latin alphabet to signify values. This numeric system was not a positional system, but an additive system in which the value of the represented number is determined by the sum of the composing symbols. The numbers 1 to 10 can be expressed in Roman numerals as follows: I, II, III, IV, V, VI, VII, VIII, IX en X. Negative numbers and zero can not be represented in the Roman numeric system. From the 14th century on, Roman numerals began to be replaced by the more convenient Arabic numerals. However, this process was gradual, and the use of Roman numerals in some minor applications continues to day as in names of kings (e.g. Louis XIV of France), in numbering schemes for annual events, and in numbering centuries in some countries (e.g. XIXe siècle).

Roman numerals, as used today, are based on seven symbols:

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

Numbers are formed by combining symbols together and adding the values, but the order of the symbols is important too. Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases, in order to avoid characters being repeated in succession (such as IIII or XXXX), these can be reduced using subtractive notation. In case a symbol is preceded by another symbol with a lower value, the lower value is subtracted from the higher value to give the value in the addition. In ancient times, the rules for writing Roman numerals have been very loose. As such, the BBC used the typographical more elegant MIM instead of MCMCIX in its subtitles to represent the year 1999.

Input

The decimal representation of the number $n \in \mathbb{N}$ (using Arabic numerals).

Output

The number $n$ represented using Roman numerals (uppercase only). The conversion of Arabic to Roman numerals can be done by traversing the table below from left to right. As long as the value $n$ is greater or equal to the integer value in the table, you append the combination of Roman numerals on the corresponding position to the Roman number. Afterwards, the value of $n$ is decremented with the integer value. As soon as $n$ is smaller than the integer value from the table, you step one position to the right in the table.

M	CM	D	CD	C	XC	L	XL	X	IX	V	IV	I
1000	900	500	400	100	90	50	40	10	9	5	4	1

The above procedure allows to uniquely convert the decimal representation of an integer into a representation using Roman numerals.

Example

Input:

Output:

MCMXCIX

In het oude Rome gebruikte men voor het weergeven van natuurlijke getallen een talstelsel gebaseerd op Romeinse cijfers. Dit talstelsel was geen positiestelsel, maar een additief stelsel waarin de waarde van het voorgestelde getal bepaald wordt door het totaal van de samenstellende symbolen. De getallen één tot en met tien worden met Romeinse cijfers geschreven als: I, II, III, IV, V, VI, VII, VIII, IX en X. Negatieve getallen en het getal nul konden niet voorgesteld worden in Romeinse cijfers. Het Romeins talstelsel raakt sinds de veertiende eeuw grotendeels in onbruik ten voordele van het decimaal talstelsel gebaseerd op Arabische cijfers. In sommige toepassingen zijn Romeinse cijfers echter nog steeds in gebruik, bijvoorbeeld bij de nummering van vorsten met dezelfde naam (bijv. Lodewijk XIV), bij de nummering van jaarlijkse events en bij de nummering van eeuwen in sommige landen (bijv. XIXe siècle).

In het talstelsel met Romeinse cijfers worden getallen genoteerd met symbolen, de eigenlijke cijfers, waarvan elk een bepaalde waarde heeft die onafhankelijk is van de positie die het cijfer in het getal inneemt. De Romeinse cijfers zijn:

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

De volgorde van de Romeinse cijfers in een getal is niet willekeurig. De waarden van de losse cijfers worden bij elkaar opgeteld, behalve als een lager cijfer vóór een hoger cijfer staat: in dat geval wordt het lagere cijfer er van afgetrokken. De regels voor het schrijven van getallen met Romeinse cijfers lijken in de Oudheid zeer los te zijn geweest. Zo gebruikte de BBC voor de aftiteling in het jaar 1999 het typografisch elegante jaartal MIM in plaats van MCMXCIX.

Invoer

De decimale voorstelling van een getal $n \in \mathbb{N}$, dus aan de hand van Arabische cijfers.

Uitvoer

Het getal $n$ voorgesteld aan de hand van Romeinse cijfers (enkel hoofdletters). De omzetting van Arabische naar Romeinse cijfers kan gebeuren door onderstaande tabel van links naar rechts te doorlopen. Zolang de waarde van $n$ groter of gelijk is aan de getalwaarde uit de tabel, voeg je de combinatie van Romeinse cijfers op de corresponderende positie achteraan toe aan het Romeins getal. De waarde van $n$ wordt daarna verlaagd met de getalwaarde. Van zodra $n$ kleiner is dan de getalwaarde uit de tabel, spring je één positie naar rechts in de tabel.

M	CM	D	CD	C	XC	L	XL	X	IX	V	IV	I
1000	900	500	400	100	90	50	40	10	9	5	4	1

Op die manier kan de decimale voorstelling van het getal op een unieke manier omgezet worden naar een voorstelling die gebruik maakt van Romeinse cijfers.

Voorbeeld

Invoer:

Uitvoer:

MCMXCIX

Submit solution!

Added by:	Peter Dawyndt
Date:	2013-09-11
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None

Informatics 1