Ограничитель запросов

Реализуйте ограничитель частоты запросов со скользящим окном в одну секунду.

Время в задаче виртуальное: оно не идёт само, а сдвигается только вызовами tick.

Интерфейс

RateLimiter(rps)          создать ограничитель: не более rps запросов
                          на каждый ключ за любое окно в 1000 мс
allow(key) -> bool        запрос по ключу key в текущий момент времени.
                          Вернуть true, если запрос разрешён (и учесть его),
                          иначе false — отклонённый запрос не учитывается
tick(ms) -> void          сдвинуть текущее время вперёд на ms миллисекунд

Начальное время — 0. Ограничение считается по скользящему окну: запрос разрешён, если за последние 1000 мс, включая текущий момент, по этому ключу было разрешено менее rps запросов.

Ограничения

• $1 \le rps \le 1000$
• не более $100000$ операций
• ключи — непустые строки латинских букв и цифр

Замечание

Окно скользящее, а не фиксированное. Реализация, обнуляющая счётчик каждую секунду, пропустит вдвое больше запросов на границе окна и не будет принята.