Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Kiến trúc máy tính] Canonical Signed Digit (NAF)

    Biểu diễn Canonical Signed Digit (CSD, hay Non-Adjacent Form – NAF) viết một số nguyên dương dưới dạng tổng các lũy thừa của 2 với hệ số thuộc {−1, 0, +1}, sao cho không có hai chữ số khác 0 nào liền kề. Đây là dạng có ít chữ số khác 0 nhất, hữu ích để tối ưu phép nhân.

    Cho số nguyên dương N, hãy in chuỗi CSD từ chữ số có trọng số cao nhất tới thấp nhất, dùng ký tự + cho +1, - cho −1, 0 cho 0 (không có số 0 thừa ở đầu), và số lượng chữ số khác 0, cách nhau bởi một dấu cách.

    Ví dụ

    N = 7 = 8 − 1 → CSD +00- (tức +2^3 −2^0), có 2 chữ số khác 0.

    • Định dạng đầu vào:

      Một dòng chứa số nguyên dương N.

    • Ràng buộc đầu vào:

      1 ≤ N ≤ 10^18.

    • Định dạng đầu ra:

      Một dòng: chuỗi CSD, dấu cách, số chữ số khác 0.

    Ví dụ:

    Đầu vào:

    7

    Đầu ra:

    +00- 2

    Giải thích:

    7 = 8 − 1 = 2^3 − 2^0, dạng CSD là +00- với 2 chữ số khác 0 (không có hai chữ số khác 0 liền kề).

    Đang tải editor...