Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Đổi số sang số La Mã

Viết một số nguyên từ 1 đến 3999 thành số La Mã.

Bạn sẽ học được gì

  • Dùng bảng giá trị xếp từ lớn đến nhỏ
  • Lặp lại lựa chọn tham lam
  • Đưa các cặp trừ vào bảng như những mục riêng

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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".

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.