Leaky Bucket (mô hình mức nước)

Thùng dung lượng C. Nước rò ra với tốc độ R đơn vị/giây. Mỗi request đến làm mức nước tăng 1. Nếu sau khi rò mà thêm 1 vẫn không vượt C thì ALLOW (mức nước +1); nếu vượt thì DENY (không thêm).

Thuật toán

Giữ level và lastT. Tại t: level = max(0, level - (t-lastT)*R), lastT=t. Nếu level + 1 <= C thì ALLOW, level += 1; ngược lại DENY.

Ví dụ

C=2, R=1: request 0,0,0 → level 1,2,DENY. t=1 rò 1 → level 1, ALLOW → 2.

Đị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 ALLOW/DENY.

solution

Đề bài: [Lập trình Web & Backend] Leaky Bucket: Tràn thùng

Leaky Bucket (mô hình mức nước)

Thuật toán

Ví dụ