Mỗi connection có một token bucket: dung lượng C token, nạp 1 token mỗi R đơn vị thời gian, bắt đầu đầy (C token). Mỗi tin tốn 1 token. Khi tin đến thời điểm t: trước hết nạp thêm token theo thời gian trôi qua kể từ lần cập nhật trước (số token nạp = floor((t - lastUpdate)/R)), giới hạn không quá C; cập nhật lastUpdate = lastUpdate + napped*R nếu có nạp (mô hình rời rạc). Nếu còn ≥1 token: chấp nhận (tốn 1), in OK <conn>; ngược lại in DROP <conn>.
Lần đầu thấy connection: bucket đầy C token, lastUpdate = t.
Dòng 1: C R. Dòng 2: N. N dòng <t> <conn> với t không giảm.
Input:
2 5
4
0 a
0 a
0 a
5 a
Output:
OK a
OK a
DROP a
OK a
Đầu C=2: 2 OK rồi hết -> DROP; tại t=5 nạp 1 token -> OK.
Dòng 1: C R. Dòng 2: N. N dòng <t> <conn>.
1 ≤ C ≤ 10^6; 1 ≤ R ≤ 10^9; 0 ≤ t ≤ 10^9; 0 ≤ N ≤ 2000.
Mỗi tin in OK <conn> hoặc DROP <conn>.
Ví dụ:
Đầu vào:
2 5
4
0 a
0 a
0 a
5 a
Đầu ra:
OK a
OK a
DROP a
OK a
Giải thích:
Đang tải editor...