Problema
I numeri romani usano I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 e M = 1000. I simboli si scrivono dal più grande al più piccolo e si sommano, tranne in sei coppie sottrattive: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 e CM = 900. Converti n nella sua forma standard, che usa sempre una coppia sottrattiva al posto di quattro simboli ripetuti (4 è IV, mai IIII).
Implementa integer_to_roman(n).
Input
n: il numero da convertire.
Output
Restituisci il numero romano come stringa di lettere maiuscole.
Vincoli
1 ≤ n ≤ 3999
Esempi
Input:
n = 1994
Output atteso:
expected = "MCMXCIV"
Input:
long long n = 1994;
Output atteso:
std::string expected = "MCMXCIV";
Input:
long n = 1994;
Output atteso:
string expected = "MCMXCIV";
Spiegazione
1000 + 900 + 90 + 4 danno M, CM, XC, IV: "MCMXCIV".
Input:
n = 58
Output atteso:
expected = "LVIII"
Input:
long long n = 58;
Output atteso:
std::string expected = "LVIII";
Input:
long n = 58;
Output atteso:
string expected = "LVIII";
Spiegazione
50 + 5 + 3 danno L, V, III: "LVIII".
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Metti in un'unica lista i simboli e le sei coppie sottrattive, ordinati per valore.
Suggerimento 2
Prendi ogni volta il valore più grande che sta ancora in quello che resta.
Suggerimento 3
Prova a mano 4, 9 e 3999 per controllare la tabella.
Complessità attesa
tempo O(1), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.