Задача 10 из 14

Римская запись с выбором

Время 5 с · память 256 МБ

Строка состоит из цифр римской системы счисления — заглавных латинских букв I, V, X, L, C, D, M. Найдите последовательность из максимального количества идущих подряд символов, которая представляет собой корректную римскую запись числа от 1 до 3999. Если найдено несколько таких последовательностей, выберите ту, которая обозначает наименьшее число. Последовательности могут перекрываться.

Корректная запись составляется слева направо из тысяч, сотен, десятков и единиц. Тысячи: пусто, M, MM, MMM. Сотни: пусто, C, CC, CCC, CD, D, DC, DCC, DCCC, CM. Десятки: пусто, X, XX, XXX, XL, L, LX, LXX, LXXX, XC. Единицы: пусто, I, II, III, IV, V, VI, VII, VIII, IX. Хотя бы один разряд должен быть непустым.

Числовые значения цифр: I — 1, V — 5, X — 10, L — 50, C — 100, D — 500, M — 1000. В парах IV, IX, XL, XC, CD и CM значение меньшей цифры вычитается, остальные значения складываются.

Входные данные

Во входных данных содержится одна непустая строка длиной не более 10610^6 символов.

Выходные данные

Выведите одно число — десятичное значение найденной последовательности римских цифр.

Примеры

Ввод 1
MMXXVI
Вывод 1
2026
Ввод 2
XXLIII
Вывод 2
43

Примечание

В первом примере подходит вся строка: MMXXVI обозначает число 2026. Во втором примере вся строка не является корректной записью, но со второго символа начинается запись XLIII числа 43.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче