eolymp
bolt
Try our new interface for solving problems
Məsələlər

Римские числа

Римские числа

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Дана строка из символов 'I', 'V', 'X', 'L', 'C', 'D' и 'M'. Требуется разбить её на несколько строк так, чтобы каждая получившаяся строка представляла собой корректное римское число, а сумма этих чисел была бы минимально возможной.

Корректным римским числом будем называть число, которое получается по следующим правилам. Сначала выписывается символ 'M' столько раз, сколько целых тысяч содержится в числе. Например, в числе 2045 содержится две целых тысячи, и его запись начнётся с символов "MM". После этого берём остаток от деления аго на 1000. В зависимости от того, сколько целых сотен содержит результат, добавляем к римской записи следующую строку: "C" - для одной сотни, "CC" - для двух, "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" - для трёх, четырёх, ..., для девяти сотен соответственно. Остаток от деления числа 2045 на 1000 равен 45. Целых сотен в нём нет, поэтому к римской записи ничего не добавляем.

Далее берём остаток от деления на 100 и, в зависимости от количества десятков в результате, по тем же правилам добавляем к римской записи "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX" или "XC" (либо ничего не добавляем, если целых десятков нет). Соответственно, для числа 2045 мы должны добавить к римской записи строку "XL".

После этого бер1тся остаток от деления на 10 исходного числа, и, в зависимости от результата, добавляется "I", "II", "III", "IV", "V", "VI", "VII", "VIII". "IX" - для 1, 2, ..., 9 соответственно, либо, в случае нулевого остатка, ничего не добавляется. для числа 2045 по этому правилу мы должны прибавить строку "V".

В итоге для числа 2045 получаем римскую запись "MMXLV".

Также на римские числа вводится дополнительное ограничение, что никакой символ в их записи не может повторяться более трёх раз подряд. То есть будем считать, что корректная римская запись существует только у чисел от 1 до 3999 включительно.

Giriş verilənləri

Во входном файле содержится одна непустая стирока длиной не более 20000 символов, состоящая из заглавных латинских букв, указанных в услоовии ('I', 'V', 'X', 'L', 'C', 'D' и 'M').

Çıxış verilənləri

В выходной файл выведите одно число - минимально возможную сумму чисел.

Nümunə

Giriş verilənləri #1
IVI
Çıxış verilənləri #1
5