Đề bài
Số La Mã dùng các ký hiệu I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 và M = 1000. Các ký hiệu được viết từ lớn đến nhỏ rồi cộng lại, trừ sáu cặp viết theo kiểu trừ: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 và CM = 900. Hãy đổi n sang dạng chuẩn, dạng này luôn dùng cặp trừ thay vì lặp một ký hiệu bốn lần (4 là IV, không bao giờ là IIII).
Hãy viết integer_to_roman(n).
Đầu vào
n: Số cần đổi.
Đầu ra
Trả về số La Mã dưới dạng chuỗi các chữ cái in hoa.
Ràng buộc
1 ≤ n ≤ 3999
Ví dụ
Đầu vào:
n = 1994
Kết quả mong đợi:
expected = "MCMXCIV"
Đầu vào:
long long n = 1994;
Kết quả mong đợi:
std::string expected = "MCMXCIV";
Đầu vào:
long n = 1994;
Kết quả mong đợi:
string expected = "MCMXCIV";
Giải thích
1000 + 900 + 90 + 4 cho M, CM, XC, IV: "MCMXCIV".
Đầu vào:
n = 58
Kết quả mong đợi:
expected = "LVIII"
Đầu vào:
long long n = 58;
Kết quả mong đợi:
std::string expected = "LVIII";
Đầu vào:
long n = 58;
Kết quả mong đợi:
string expected = "LVIII";
Giải thích
50 + 5 + 3 cho L, V, III: "LVIII".
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Liệt kê các ký hiệu cùng sáu cặp trừ trong một bảng, sắp theo giá trị.
Gợi ý 2
Lặp lại việc lấy giá trị lớn nhất còn vừa với phần còn lại.
Gợi ý 3
Thử bằng tay với 4, 9 và 3999 để kiểm tra bảng của bạn.
Độ phức tạp mong đợi
thời gian O(1), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.