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:
1999
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:
1999
Uitvoer:
MCMXCIX
| 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 |
RSS