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] Token bucket shaping

    Bộ điều hình lưu lượng token bucket: tốc độ nạp rate token/giây, dung lượng tối đa cap token. Gáo đầy cap token ở thời điểm 0.

    Các gói đến lần lượt với thời điểm t (giây, không giảm) và kích thước size token. Khi một gói đến:

    1. Nạp thêm (t − t_trước) * rate token, nhưng không vượt cap.
    2. Nếu số token hiện có ≥ size: trừ size token, gói PASS.
    3. Ngược lại: gói DROP (không trừ token).

    In PASS/DROP cho từng gói theo thứ tự. Chỉ dùng thư viện chuẩn. Dùng số thực để tính token.

    Ví dụ

    rate=1, cap=10, gói đầu t=0 size=10 → đủ token → PASS, còn 0 token.

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

      Dòng đầu rate cap n. n dòng sau: t size (t không giảm dần).

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

      0 < rate ≤ 10^6. 0 < cap ≤ 10^6. 1 ≤ n ≤ 100000. 0 ≤ t ≤ 10^6. 0 < size ≤ cap.

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

      In n dòng, mỗi dòng PASS hoặc DROP.

    Ví dụ:

    Đầu vào:

    1 10 3
0 10
0 1
5 5

    Đầu ra:

    PASS
DROP
PASS

    Giải thích:

    t=0 gáo đầy 10, gói size10 → PASS còn 0. t=0 size1: chưa nạp thêm, 0<1 → DROP. t=5: nạp 5 token, size5 → PASS còn 0.

    Đang tải editor...