Задача №114187. Римские числа
Один древнеримский торговец брал несколько раз ссуду в древнеримском банке. Каждый раз банкир записывал размер выданной ссуды на листе пергамента, используя римские числа. Но ввиду дороговизны пергамента запись производилась плотно и все числа оказались записанными подряд, без разделителей. Когда торговец пришёл возвращать ссуду, оказалось, что невозможно установить разбиение записи на числа.
Например, если на пергаменте записана строка «XIIV», её можно разбить на римские числа разными способами, например, XI + IV = 11 + 4 = 15 или XII + V = 12 + 5 = 17, возможны и другие варианты разбиения.
Торговец хочет вернуть как можно меньше денег, поэтому он хочет так разбить строк у цифр на римские числа, чтобы сумма всех чисел была как можно меньше.
Программа получает на вход строку, длина которой не превосходит 250 символов. Строка состоит только из заглавных латинских букв I, V, X, L, С, D, M.
Программа должна вывести единственное число – минимально возможную сумму, которую можно получить при разбиении данной строки на последовательность корректных римских чисел. Ответ нужно вывести арабскими цифрами в десятичной системе счисления.
Римскими цифрами можно записать целые числа от 1 до 3999. Число представляется в виде суммы тысяч, сотен, десятков и единиц. Далее из следующей таблицы берётся по одному элементу, соответствующему тысячам, сотням, десяткам, единицам ровно в таком
порядке.
| Цифра |
Тысячи |
Сотни |
Десятки |
Единицы |
|---|---|---|---|---|
| 1 | M |
C | X | I |
| 2 | MM | CC | XX | II |
| 3 | MMM | CCC | XXX | III |
| 4 | CD | XL | IV | |
| 5 | D | L | V | |
| 6 | DC | LX | VI | |
| 7 | DCC | LXX | VII | |
| 8 | DCCC | LXXX | VII | |
| 9 | CM | XC | IX |
Если число тысяч, сотен, десятков, единиц равно 0, то из соответствующего столбца ничего не берётся. Например, число 1990 записывается, как 1000 + 900 + 90 = MCMXС.
Решение, правильно работающее только для случаев, когда входная строка содержит только символы I, V», её можно разбить на римские, X, будет оцениваться в 30 баллов.
Решение, правильно работающее только для случаев, когда входная строка содержит только символы I, V», её можно разбить на римские, X, L, C, будет оцениваться в 60 баллов.
XIIV
15