410601: GYM104064 I IXth Problem
Description
Emily recently learned about the Roman Empire and its civilization at school. One aspect that was especially fascinating to her is the number system that they used, the Roman numerals. The Roman number system uses seven distinct digits, each representing a different value and denoted by a letter, where I is $$$1$$$, V is $$$5$$$, X is $$$10$$$, L is $$$50$$$, C is $$$100$$$, D is $$$500$$$ and M is $$$1\,000$$$. Multiples of $$$1$$$, $$$10$$$, $$$100$$$ and $$$1\,000$$$ are then written according to the following table:
$$$\times$$$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
$$$1$$$ | I | II | III | IV | V | VI | VII | VIII | IX |
$$$10$$$ | X | XX | XXX | XL | L | LX | LXX | LXXX | XC |
$$$100$$$ | C | CC | CCC | CD | D | DC | DCC | DCCC | CM |
$$$1\,000$$$ | M | MM | MMM |
Each number from $$$1$$$ to $$$3\,999$$$ is written as a combination of numerals from the table, using at most one numeral from each row and going from bottom to top. For instance, $$$2\,021$$$ is MMXXI and $$$594$$$ is DXCIV. Note that in this number system it is not possible to write numbers greater than $$$3\,999$$$ and also that subtractive notation can only be used in the six cases above (e.g. IC is not considered a valid Roman numeral).
Emily found a bunch of old Scrabble sets in her attic. She threw out all the tiles with letters other than the Roman digits and started forming Roman numerals from the remaining tiles. It is easy to form valid numerals from the tiles by using just one tile per numeral, but what is the minimal number of numerals that can be formed while still using all the available tiles?
InputThe input consists of:
- One line with seven integers $$$m$$$, $$$d$$$, $$$c$$$, $$$\ell$$$, $$$x$$$, $$$v$$$ and $$$i$$$ ($$$0 \le m,d,c,\ell,x,v,i \le 10^{18}$$$), which respectively are the number of M, D, C, L, X, V and I tiles that must be used.
Output an integer $$$n$$$, the minimal possible number of Roman numerals that can be formed while using all of the tiles in the input. Then output an optimal solution in the following format.
- An integer $$$k$$$, the number of distinct Roman numerals used in this solution.
- $$$k$$$ pairs of a Roman numeral and a positive integer indicating how often this numeral is used in this solution.
4 1 7 1 3 1 3Output
2 2 MMDCCCLXX 1 MMCCCXCVIII 1Input
0 0 0 300 2000 1000 2100Output
1000 2 XXVIII 700 LXXV 300