Конвейер с ограниченными буферами
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Темы
- Асинхронность и потоки
- Стек, очередь, связные списки
Предметы 0, 1, …, n − 1 проходят m этапов по порядку: этап 0, затем 1, …, затем m − 1. На этапе s есть limits[s] мест, то есть одновременно на нём обрабатывается не больше limits[s] предметов; предмет i проводит на этапе s ровно stage_times[i][s] мс. В момент 0 все предметы готовы к этапу 0 и входят в него по возрастанию индекса.
Между этапами s и s + 1 есть очередь. Предмет, закончивший этап s, встаёт в её конец. Первые buffers[s] предметов очереди лежат в буфере, а остальные заблокированы: каждый из них продолжает занимать своё место на этапе s, и это место не может взять новый предмет. Этап берёт предметы строго в порядке очереди: как только у него есть свободное место и очередь перед ним не пуста, он сразу забирает её первый предмет. Когда первый предмет уходит, следующий заблокированный в тот же момент переходит в буфер и освобождает своё место; такая цепочка переходов может мгновенно пройти назад через несколько этапов. После последнего этапа предмет сразу покидает конвейер.
Если несколько предметов заканчивают этап в один момент, они встают в очередь по возрастанию индекса, и все это происходит до того, как в этот момент занимаются свободные места.
Верните для каждого предмета (по порядку индексов) момент, когда он покинул последний этап, в мс от начала. Функция асинхронная: удобно обрабатывать события по времени и ждать каждого таймером; текущее время в миллисекундах: Date.now() в JS/TS и round(asyncio.get_running_loop().time() * 1000) в Python. В тестах ожидания идут по виртуальным часам и не занимают реального времени. Ограничения: до 30 предметов, 1 ≤ m ≤ 5, в каждом stage_times[i] ровно m чисел от 1 до 100000, в limits — m чисел от 1 до 10, в buffers — m − 1 чисел от 0 до 10. Если предметов нет, верните [].
Пример: stage_times = [[1, 5], [1, 5], [1, 5]], limits = [1, 1], buffers = [0] → [6, 11, 16] (предмет 1 заканчивает этап 0 в момент 2 и занимает единственное место этапа 0 до момента 6, поэтому предмет 2 начинает этап 0 только в момент 6).
Источник: задача CodeShare