Задача 89
Римские цифры

Правила записи чисел римскими цифрами позволяют записывать одно и то же число несколькими способами (см. FAQ: Римские числа). Однако, всегда существует "наилучший" способ записи определенного числа.

К примеру, ниже представлены все разрешенные способы записи числа шестнадцать:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

Последнее из них считается наиболее эффективным, поскольку использует наименьшее число римских цифр.

В текстовом файле roman.txt (щелкнув правой кнопкой мыши, выберите 'Save Link/Target As...') размером 11KБ тысяча чисел записана римскими цифрами правильным, но не обязательно наилучшим способом, т.е. они отсортированы в порядке убывания и подчиняются правилу вычитания пар (для информации об определяющих правилах данной задачи см. FAQ).

Найдите число символов, сэкономленных путем перезаписи каждого числа в его наиболее короткий вид.

Примечание: Можете считать, что все числа в файле содержат не более четырех последовательных одинаковых цифр.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net