Problema
Os algarismos romanos usam I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 e M = 1000. Os símbolos são escritos do maior para o menor e somados, com exceção de seis pares subtrativos: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 e CM = 900. Converta n para a forma padrão, que sempre usa um par subtrativo em vez de quatro símbolos repetidos (4 é IV, nunca IIII).
Implemente integer_to_roman(n).
Entrada
n: o número a ser convertido.
Saída
Retorne o número romano como uma string de letras maiúsculas.
Restrições
1 ≤ n ≤ 3999
Exemplos
Entrada:
n = 1994
Saída esperada:
expected = "MCMXCIV"
Entrada:
long long n = 1994;
Saída esperada:
std::string expected = "MCMXCIV";
Entrada:
long n = 1994;
Saída esperada:
string expected = "MCMXCIV";
Explicação
1000 + 900 + 90 + 4 dá M, CM, XC, IV: "MCMXCIV".
Entrada:
n = 58
Saída esperada:
expected = "LVIII"
Entrada:
long long n = 58;
Saída esperada:
std::string expected = "LVIII";
Entrada:
long n = 58;
Saída esperada:
string expected = "LVIII";
Explicação
50 + 5 + 3 dá L, V, III: "LVIII".
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Liste os símbolos e os seis pares subtrativos juntos, ordenados por valor.
Dica 2
Pegue repetidamente o maior valor que ainda cabe no que falta.
Dica 3
Teste 4, 9 e 3999 à mão para conferir a sua tabela.
Complexidade esperada
tempo O(1), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.