В римской записи I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 и M = 1000. Символы пишутся от большего к меньшему, и их значения складываются. Исключение составляют шесть вычитательных пар: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 и CM = 900. Переведите n в стандартную запись, где вместо четырёх одинаковых символов подряд всегда используется вычитательная пара (4 - это IV, а не IIII).
Реализуйте integer_to_roman(n).
Входные данные
n: число, которое нужно перевести.
Выходные данные
Верните римскую запись числа в виде строки из заглавных букв.
Ограничения
1 ≤ n ≤ 3999
Примеры
Ввод:
n = 1994
Ожидаемый вывод:
expected = "MCMXCIV"
Ввод:
long long n = 1994;
Ожидаемый вывод:
std::string expected = "MCMXCIV";
Ввод:
long n = 1994;
Ожидаемый вывод:
string expected = "MCMXCIV";
Пояснение
1000 + 900 + 90 + 4 дают M, CM, XC, IV: "MCMXCIV".
Ввод:
n = 58
Ожидаемый вывод:
expected = "LVIII"
Ввод:
long long n = 58;
Ожидаемый вывод:
std::string expected = "LVIII";
Ввод:
long n = 58;
Ожидаемый вывод:
string expected = "LVIII";
Пояснение
50 + 5 + 3 дают L, V, III: "LVIII".
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Запишите символы и шесть вычитательных пар в одну таблицу, упорядочив их по значению.
Подсказка 2
Раз за разом берите наибольшее значение, которое ещё помещается в остаток.
Подсказка 3
Проверьте таблицу, переведя вручную 4, 9 и 3999.
Ожидаемая сложность
время O(1), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.