Все задачи
Средне Решено: 0 Процент решений: 0%

Перевод числа в римскую запись

Запишите целое число от 1 до 3999 римскими цифрами.

Чему вы научитесь

  • Использовать таблицу значений, упорядоченную по убыванию
  • Многократно применять жадный выбор
  • Хранить вычитательные пары как обычные строки таблицы

Условие

В римской записи 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

Примеры

Пример 1
Ввод:
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".

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

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