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: Cho phép / từ chối

    Token Bucket cơ bản

    Thùng token có dung lượng tối đa C, nạp R token mỗi giây (R nguyên). Ban đầu (tại thời điểm request đầu tiên) thùng đầy = C. Mỗi request tiêu tốn 1 token.

    Thuật toán

    Giữ tokens và lastT. Khi có request tại t: nạp tokens = min(C, tokens + (t - lastT) * R), đặt lastT = t. Nếu tokens >= 1 thì ALLOW và tokens -= 1; ngược lại DENY.

    Ví dụ

    C=2, R=1: tại t=0 thùng đầy 2. Request 0,0,0 → ALLOW,ALLOW,DENY. Tại t=2 nạp lại đủ → ALLOW.

    • Đị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; 0 ≤ t ≤ 1e9.

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

      Q dòng ALLOW/DENY.

    Ví dụ:

    Đầu vào:

    2 1
4
0
0
0
2

    Đầu ra:

    ALLOW
ALLOW
DENY
ALLOW

    Giải thích:

    Đầy 2 token: 2 request đầu ALLOW, request 3 DENY. t=2 nạp +2 → ALLOW.

    Đang tải editor...