Хроники велоспорта
Я тут столкнулся с одной задачей. Есть система реального времени, живущая по циклическому расписанию, состоящем из бесконечной последовательности периодов. В каждом периоде работает T потоков; порядок их выполнения внутри периода неизвестен и не обязан быть постоянным. Каждый поток отправляет куда-то сообщения. За один период все потоки в сумме должны отправить M сообщений, а среднее число сообщений, отправленных каждым потоком за один период, должно стремиться к M/T. Нужен алгоритм, который позволяет каждому потоку в каждом периоде определить количество отправляемых им сообщений. Памяти можно использовать O(T).
Решить мне удалось ее удивительно легко (могу написать, если интересно), поэтому логично было предположить, что она уже решена. Но беглый гуглеж не позволил найти мне известное решение, и это меня слегка беспокоит. Возможно, кто-нибудь из френдов сталкивался и знает где копать?
UPD. Виноват, забыл указать еще условие. Количество сообщений, отправленных любыми двумя потоками за один период, не должно различаться более чем на 1. Без этого условия решение элементарно: в каждом периоде один поток (выбираемый по кругу) отправляет M, а остальные - 0.
Решить мне удалось ее удивительно легко (могу написать, если интересно), поэтому логично было предположить, что она уже решена. Но беглый гуглеж не позволил найти мне известное решение, и это меня слегка беспокоит. Возможно, кто-нибудь из френдов сталкивался и знает где копать?
UPD. Виноват, забыл указать еще условие. Количество сообщений, отправленных любыми двумя потоками за один период, не должно различаться более чем на 1. Без этого условия решение элементарно: в каждом периоде один поток (выбираемый по кругу) отправляет M, а остальные - 0.