#P12279. Distributed Rate Limiting
Distributed Rate Limiting
Distributed Rate Limiting
Little Blue has recently developed an OpenAPI for his service. To prevent malicious abuse, he needs to implement a distributed rate limiting component.
Specifically, in each time interval ([k \cdot N, (k+1) \cdot N)) (with (k = 0, 1, 2, \ldots)), the API is allowed at most (M) successful requests. Any request exceeding this limit should be considered a failure.
Given a list of timestamps representing the moments when a client made API requests, determine how many of these requests were successful.
inputFormat
The first line contains three integers (T), (N), and (M), where (T) is the number of timestamps, (N) defines the length of each time interval, and (M) is the maximum allowed successful requests per interval. The second line contains (T) space-separated integers representing the API request timestamps.
outputFormat
Output a single integer representing the number of successful API requests.
sample
5 10 2
1 2 11 12 13
4
</p>