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

@element_of_death · Регистрация: 28.12.2008

Студворк — интернет-сервис помощи студентам

Написать компонент, отвечающий за ограничение запросов пользователей к сервису.
Характеристики компонента — лимит запросов на пользователя, лимит запросов на сервис и продолжительность интервала (duration), за который учитываются запросы. Запрос к сервису, поступивший в момент времени time, отклоняется, если он удовлетворяет хотя бы одному из двух условий:
Если в промежутке времени [time−duration, time] от данного пользователя было принято к выполнению не меньше пользовательского лимита запросов — должен возвращаться код ошибки «Too Many Requests».
Если в промежутке времени [time−duration,time] суммарно от всех пользователей было принято к выполнению не меньше сервисного лимита запросов — должен возвращаться код ошибки «Service Unavailable».

Условия проверяются последовательно друг за другом, пока не будет найдено первое условие, которому запрос удовлетворяет. Если запрос не удовлетворяет ни одному условию, то он выполняется.

Формат ввода
Программа получает на вход строку с тремя числами, разделенными пробелами:
userLimit (1≤userLimit≤5⋅10**4) — лимит запросов на пользователя,
serviceLimit (1≤serviceLimit≤5⋅10**4) — лимит запросов на сервис,
duration (1≤duration≤10**9) — промежуток времени в миллисекундах, за который учитываются запросы для расчета лимитов.
В следующих строках поступают описания запросов. Каждый запрос представлен двумя разделенными пробелом числами:
time (1≤time≤10**9) — время поступления запроса,
userId (1≤userId≤10**9) — идентификатор пользователя, выполнившего запрос.
Входные данные завершаются строкой с числом −1. Гарантируется, что все времена в описании запросов не убывают, а количество запросов не превышает 5⋅10**4.
Тестирующая система даст прочитать очередной запрос только после записи в стандартный вывод ответа на предыдущий запрос.

Формат вывода
Для каждого запроса необходимо вывести один из трех кодов ответа HTTP:
200 — если запрос будет выполнен.
429 — если запрос будет отклонен из-за превышения лимита запросов пользователем.
503 — если запрос будет отклонен из-за превышения сервисного лимита запросов.
Не забывайте о том, что ваша программа должна сбрасывать буфер вывода после вывода строчки с тайм-аутом. Для сброса буфера вывода можно использовать fflush(stdout) в C++, System.out.flush() в Java, stdout.flush() в Python.

Пример
Ввод
2 5 5
1 100
1 100
2 100
2 200
2 300
2 400
2 500
3 500
5 200
6 100
7 200
-1

Вывод
200
200
429
200
200
200
503
503
503
429
200

Мой код, но где-то ошибка:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def request_limmit():
    user_limit, service_limit, duration = map(int, input().split())
    users = {}
    bad_requests = []
 
    while True:
        n = input()
        if n == '-1':
            break
 
        our_time, user_id = map(int, n.split())
        if user_id in users:
            users[user_id].append(our_time)
        else:
            users[user_id] = [our_time]
 
        time = our_time - duration
        for i_user in users:
            for elem in users[i_user]:
                if elem == time:
                    users[i_user].remove(elem)
 
        for req in bad_requests:
            if req == time:
                bad_requests.remove(req)
 
        users_requests = 0
        for i_key, i_value in users.items():
            users_requests += len(i_value)
        users_requests -= len(bad_requests)
 
        if len(users[user_id]) > user_limit:
            print(429)
            bad_requests.append(our_time)
        elif users_requests > service_limit:
            print(503)
            users[user_id].remove(our_time)
        else:
            print(200)
 
 
request_limmit()

@eaa · 29.01.2023, 19:05

element_of_death, какая ошибка?

@element_of_death · 29.01.2023, 19:11 **[ТС]**

ну типо в яндекс-контесте первый тест прошёл, второй не прошёл, я хз ) А тесты там скрыты кроме первого

@eaa · 29.01.2023, 19:12

element_of_death, вердикт то какой на тесте?

@element_of_death · 29.01.2023, 19:17 **[ТС]**

WA, неверный ответ

@eaa · 30.01.2023, 11:37

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
user_limit, service_limit, duration = map(int, input().split())
users = {}
requests = []
prev_time = 0
for s in iter(input, '-1'):
    curr_time, user_id = map(int, s.split())
    if curr_time - prev_time > duration:
        requests = [t for t in requests if curr_time - t <= duration]
        if requests:
            prev_time = requests[0]
    if user_id in users:
        users[user_id] = [t for t in users[user_id] if curr_time - t <= duration]
    if len(requests) >= service_limit:  # превышения сервисного лимита запросов
        if user_id in users and len(users[user_id]) >= user_limit:  # превышения лимита запросов польз
            print(429)
        else:
            print(503)
    else:
        if user_id in users and len(users[user_id]) >= user_limit:  # превышения лимита запросов польз
            print(429)
        else:
            users.setdefault(user_id, []).append(curr_time)
            requests.append(curr_time)
            print(200)  # выполнено

Новые блоги и статьи Все статьи Все блоги /
Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных через динамический список в справочнике Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.01.2023, 19:05
	element_of_death, какая ошибка? 0

@element_of_death 0 / 0 / 0 Регистрация: 28.12.2008 Сообщений: 7
	29.01.2023, 19:11 [ТС]
	ну типо в яндекс-контесте первый тест прошёл, второй не прошёл, я хз ) А тесты там скрыты кроме первого 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.01.2023, 19:12
	element_of_death, вердикт то какой на тесте? 0

@element_of_death 0 / 0 / 0 Регистрация: 28.12.2008 Сообщений: 7
	29.01.2023, 19:17 [ТС]
	WA, неверный ответ 0

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

Решение