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

    solution

    Đề bài: [Lập trình Web & Backend] Token Bucket: Số token còn lại

    Token Bucket — báo số token còn lại

    Như Token Bucket cơ bản (dung lượng C, nạp R/giây, đầy lúc đầu). Sau khi xử lý mỗi request, in số token còn lại (làm tròn xuống, dạng số nguyên). Request bị DENY không trừ token.

    Thuật toán

    Nạp token, kẹp ở C. Nếu tokens >= 1: trừ 1 (ALLOW). In floor(tokens).

    Ví dụ

    C=3, R=1, request tại 0,0,0,0: token sau mỗi lần = 2,1,0,0.

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

      Dòng 1: C R. Dòng 2: Q. Q dòng timestamp không giảm.

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

      1 ≤ C ≤ 1e9; 1 ≤ R ≤ 1e6; 1 ≤ Q ≤ 1000.

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

      Q dòng, mỗi dòng số token còn lại (số nguyên).

    Ví dụ:

    Đầu vào:

    3 1
4
0
0
0
0

    Đầu ra:

    2
1
0
0

    Giải thích:

    Đầy 3: trừ dần 2,1,0; request 4 không đủ token → vẫn 0.

    Đang tải editor...