1708: Римські числа

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 30
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Один давньоримський торговець брав декілька разів позику в банку. Кожен раз банкір записував розмір виданої позики на аркуші пергаменту, використовуючи римські числа. Але з огляду на дорожнечу пергаменту запис проводився щільно і всі числа виявилися записаними підряд, без роздільників. Коли торговець прийшов повертати позику, виявилося, що неможливо встановити розбиття запису на числа.

Наприклад, якщо на пергаменті записаний рядок «XIIV», його можна розбити на римські числа різними способами: XI + IV = 11 + 4 = 15 або XII + V = 12 + 5 = 17. Можливі й інші варіанти розбиття.

Торговець хоче повернути якомога менше грошей, тому він хоче так розбити рядок цифр на римські числа, щоб сума всіх чисел була найменшою.

Формат вхідних даних

Програма отримує на вхід рядок, довжина якого не перевищує 250 символів. Рядок складається тільки з великих латинських літер I, V, X, L, С, D, M.

Формат вихідних даних

Програма повинна вивести єдине число - мінімально можливу суму, яку можна отримати при розбитті цього рядка на послідовність коректних римських чисел. Відповідь потрібно вивести арабськими цифрами в десятковій системі числення.

Примітка

Римськими цифрами можна записати цілі числа від 1 до 3999. Число представляється у вигляді суми тисяч, сотень, десятків і одиниць. Далі з наступної таблиці береться по одному елементу, що відповідають тисячам, сотням, десяткам, одиницям в такому порядку.

Приклад вхідних даних

XIIV

Приклад вихідних даних

15

Коментарі

Ще немає коментарів.