Однажды Артёму заблокировали канал на одном из видеохостингов. «Ну заблокировали и заблокировали», — подумал он и решил перезалить свои видеоролики на другие видеохостинги. Артём решил подойти к этому процессу с исследовательской точки зрения, чтобы выяснить, какой видеохостинг лучше. Для начала Артём решил, что каждый видеоролик он загрузит ровно на один видеохостинг, чтобы у его зрителей была мотивация подписываться на все видеохостинги. Ведь, если на какой-то видеохостинг подпишется сильно больше или меньше зрителей, то это может исказить статистику просмотров. Далее Артём решил, что минимальное и максимальное число загруженных им видеороликов на каждый видеохостинг должны отличаться как можно меньше. Ведь, если на если на какой-то видеохостинг будет загружено сильно больше или меньше видеороликов, то это также может исказить статистику просмотров. Артём уже собрался загружать видеоролики на видеохостинги, но заметил, что каждый видеоролик можно отнести ровно к одной теме. Разные темы могут быть интересны разным зрителям. Поэтому Артём решил, что для ещё большей равномерности нужно загрузить видеоролики так, чтобы для каждой тематики минимальное и максимальное число загруженных видеороликов этой темы на каждом видеохостинге также отличалось как можно меньше. Артём понял, что он слишком переусложнил себе задачу и без вашей помощи ему теперь не справиться. Максимум баллов за задачу - 100. Формат входных данных Первая строка содержит три натуральных числа N , M , K ( 1 ≤ N ≤ 10 5 , 1 ≤ M , K ≤ N ) — число видеороликов, тем и видеохостингов. Все они пронумерованы с единицы. Вторая строка содержит N натуральных чисел t i ( 1 ≤ t i ≤ M ) — тема i -го видеоролика. Формат выходных данных Выведите K строк. Каждая строка x должна начинаться с целого числа S — числа видеороликов, загруженных на видеохостинг с номером x . Далее идут S целых чисел — номера соответствующих видеороликов. Пример 1 Входные данные 10 4 3 1 2 2 3 3 3 4 4 4 4 Выходные данные 4 1 4 7 10 3 2 5 8 3 3 6 9

Ниже предлагаю пошаговый алгоритм решения задачи и объяснение, как получить требуемое разбиение видео по hosting-площадкам с учетом двух критериев баланса: по количеству на каждом хосте и по распределению тем внутри каждого хоста. Задача в сжатом виде: - Есть N видеороликов, у каждого свой темы t_i (1..M). - Нужно распределить все видео по K хостингам так, чтобы: - числа видео на хостингах различались минимально (идеально: на каждом хосте получалось бы либо floor(N/K), либо ceil(N/K) видео); - для каждой темы распределение по хостингам было как можно более равномерным (для каждой темы counts по хостингам различались минимально). Алгоритм (практичный и реализуемый за O(N log K)) 1) Подготовка целевого размера хостов - Пусть base = N div K, extra = N mod K. - Для хоста h (1 ≤ h ≤ K) задаём целевой размер: sizes[h] = base + (h ≤ extra ? 1 : 0). - Остаток по каждому хосту rem[h] = sizes[h]. - Это гарантирует, что диапазон между максимально заполненным и минимально заполненным хостом не превышает 1. 2) Группировка видео по теме - Создаём список видеороликов для каждой темы j = 1..M: videos_of_topic[j]. - Заполняем их по входящим данным t_i. 3) Распределение по темам с балансировкой - Для каждой темы j от 1 до M: - Пусть vids = videos_of_topic[j], их количество c = |vids|. - Если c = 0, пропускаем тему. - Для этого Thema будем распределять её видеоролики по хостам таким образом, чтобы число видеороликов данной темы на каждом хосте было как можно ближе друг к другу, не превышая доступный остаток на хостах. - Вводим локальные счётчики для темы j: curCnt[h] — сколько видеороликов темы j уже назначено на хост h. Инициализируем их нулями. - Вводим минимальную кэш-очередь (min-heap) из хостов, у которых ещё есть место (rem[h] > 0). Элемент кучи для хоста h содержит пару (curCnt[h], h). - Для каждого видео из vids (в любом порядке, например, по их порядку в входе): - Достаём из кучи хост h с минимальным curCnt[h]. Чтобы выбрать корректного хоста, поддерживаем проверку валидности (в кучу могут попадать устаревшие пары). - Назначаем текущее видео на хост h: add video_id в список хостa h; уменьшаем rem[h]--, увеличиваем curCnt[h]++. - Если rem[h] > 0, заново кладём в кучу обновлённую пару (curCnt[h], h). - Таким образом, для данной темы распределение по хостам будет максимально сбалансированным с учётом текущей свободной ёмкости. 4) Проверка и выход - После обработки всех тем у каждого хоста будет ровно sizes[h] видео, разница между максимумом и минимумом не более 1. - Выводим K строк, для каждого хоста h сначала S = количество его видео, затем перечисляем номера этих видео. Сложность - Время: O(N log K) — каждое видео обслуживается операцией в минимальной куче по K элементам. - Память: O(N) для хранения принадлежности видео к хостам и сами списки. Псевдокод (практически готов к реализации) - Вход: N, M, K - t[1..N] - groups[j] = пустой список для j = 1..M - для i = 1..N: groups[t[i]].append(i) - base = N div K, extra = N mod K - sizes[h] = base + (h <= extra ? 1 : 0) для h = 1..K - rem[h] = sizes[h] - answer[h] = пустой список - для j = 1..M: vids = groups[j] если vids пусто: продолжить curCnt[h] = 0 для всех h создание пустой min-heap H для h = 1..K: если rem[h] > 0: push (0, h) в H p = 0 while p < len(vids): пока H не пуст и (rem[H.top.h] == 0 или H.top.cnt != curCnt[H.top.h]): pop из H если H пуст: break (чаще не произойдёт) (cnt, h) = pop из H video_id = vids[p] answer[h].append(video_id) rem[h]-- curCnt[h]++ p++ если rem[h] > 0: push (curCnt[h], h) в H - Вывод: для h = 1..K print len(answer[h]) и далее номера видео из answer[h] через пробел Пояснения к примеру - В примере N=10, K=3, M=4. base=3, extra=1 → sizes = [4,3,3]. - Алгоритм распределяет видео так, чтобы: - на хост 1 было 4 видео, на хостах 2 и 3 — по 3; - для каждой темы баланс по хостам близок к равному распределению; - итоговое распределение похоже на пример:: хост 1: видеоролики [1, 4, 7, 10] хост 2: [2, 5, 8] хост 3: [3, 6, 9] Это удовлетворяет условиям задачи: минимальная разница между количеством на хостах и сбалансированное распределение по темам. Дополнительные варианты и примечания - Точки зрения на разбиение могут немного различаться в зависимости от выбора порядка обработки тем и поведения кучи при равенстве ключей. Все такие варианты остаются корректными и удовлетворяют требования. - Можно реализовать аналогично и без кучи, если у K небольшое значение, но для больших K предпочтительнее использовать кучу для эффективного выбора минимального curCnt[h] среди доступных хостов. Если хочешь, могу привести готовый код на Python или C++, чтобы просто скопировать и запустить.