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

    solution

    Đề bài: [Mạng máy tính] Aggregate tối thiểu CIDR

    Cho n khối CIDR, hãy biểu diễn hợp (union) của chúng bằng số khối CIDR ít nhất.

    Thuật toán: chuyển mỗi CIDR thành khoảng số nguyên [lo, hi]; sắp xếp, gộp các khoảng phủ nhau hoặc liền kề; với mỗi khoảng kết quả, sinh dãy CIDR tối thiểu (greedy: tại địa chỉ cur, chọn khối lớn nhất căn lề đúng (cur & -cur) mà không vượt quá phần còn lại).

    In các CIDR theo thứ tự địa chỉ tăng dần. Tự xử lý bit, không dùng ipaddress.

    Ví dụ

    192.168.0.0/24 và 192.168.1.0/24 kề nhau và căn lề → gộp thành 192.168.0.0/23.

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

      Dòng đầu n. n dòng sau, mỗi dòng một khối CIDR ip/prefix.

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

      1 ≤ n ≤ 1000. 0 ≤ prefix ≤ 32.

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

      In các khối CIDR tối thiểu, mỗi khối một dòng, theo địa chỉ tăng dần.

    Ví dụ:

    Đầu vào:

    2
192.168.0.0/24
192.168.1.0/24

    Đầu ra:

    192.168.0.0/23

    Giải thích:

    Hai /24 kề nhau và .0.0 căn lề /23 → gộp thành một khối 192.168.0.0/23.

    Đang tải editor...