e-olymp 7. Римские числа

Постановка задачи

e-olymp 7. Римские числа

Посчитать сумму двух натуральных чисел A и B, записанных в римской системе счисления. Ответ также записать в римской системе счисления.
M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5, I = 1. Все числа – не превышают 2000.

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

В строке записано два числа в римской системе счисления, между которыми стоит знак + .

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

Единственное число – сумма чисел, записанное также в римской системе счисления. Числа в римской системе счисления записаны большими латинскими буквами.

Алгоритм решения

Считываем два числа и представляем каждое из них в десятичной системе счисления. Чтобы перевести число из римской системы в десятичную, нужно изначально считать, что в десятичной системе оно равно нулю. Это число будет нашим результатом. Далее, нужно перебрать все цифры римского числа, следуя таким правилам:

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

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

Вспомогательные числа
В римской системе счисления В десятичной системе счисления
1 I
4 IV
5 V
9 IX
10 X
40 XL
50 L
90 XC
100 C
400 CD
500 D
900 CM
1000 M

Выбираем самое последнее число из таблицы, которое является самым большим, и, пока оно не превышает суммы, вычитаем из суммы это число и выводим выбраное число в римской системе счисления. Далее выбираем предыдущее число и проделываем аналогичные действия. Эти действия проделываем до тех пор, пока сумма не окажется равной нулю. Таким образом мы получим сумму, представленную в римской системе счисления.

Тесты

Входные данные Выходные данные
I+I II
IV+VIII XII
MM+CXC MMCXC
CXCIX+I CC

Реализация

ideone: ссылка
Засчитаное решение на e-olymp: ссылка

 

Добавить комментарий