Однажды Артёму заблокировали канал на одном из видеохостингов. «Ну заблокировали и…
- User
Однажды Артёму заблокировали канал на одном из видеохостингов. «Ну заблокировали и заблокировали», — подумал он и решил перезалить свои видеоролики на другие видеохостинги. Артём решил подойти к этому процессу с исследовательской точки зрения, чтобы выяснить, какой видеохостинг лучше.
Для начала Артём решил, что каждый видеоролик он загрузит ровно на один видеохостинг, чтобы у его зрителей была мотивация подписываться на все видеохостинги. Ведь, если на какой-то видеохостинг подпишется сильно больше или меньше зрителей, то это может исказить статистику просмотров.
Далее Артём решил, что минимальное и максимальное число загруженных им видеороликов на каждый видеохостинг должны отличаться как можно меньше. Ведь, если на если на какой-то видеохостинг будет загружено сильно больше или меньше видеороликов, то это также может исказить статистику просмотров.
Артём уже собрался загружать видеоролики на видеохостинги, но заметил, что каждый видеоролик можно отнести ровно к одной теме. Разные темы могут быть интересны разным зрителям. Поэтому Артём решил, что для ещё большей равномерности нужно загрузить видеоролики так, чтобы для каждой тематики минимальное и максимальное число загруженных видеороликов этой темы на каждом видеохостинге также отличалось как можно меньше.
Артём понял, что он слишком переусложнил себе задачу и без вашей помощи ему теперь не справиться.
Максимум баллов за задачу - 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 целых чисел — номера соответствующих видеороликов.
- Assistant
Чтобы решить задачу, необходимо распределить видеоролики по видеохостингам с учётом двух основных условий:
-
Балансировка общего количества видеороликов на каждом видеохостинге: Общее количество видеороликов должно быть распределено максимально равномерно между всеми видеохостингами. Это значит, что разница между количеством видеороликов на самом загруженном и самом слабозагруженном видеохостинге должна быть минимально возможной.
-
Балансировка количества видеороликов по каждой теме на каждом видеохостинге: Для каждой темы разница между количеством видеороликов этой темы на разных видеохостингах также должна быть минимально возможной.
Алгоритм решения:
-
Сбор данных по темам:
- Для каждой темы
jопределить количество видеороликовC_j. - Собрать список видеороликов для каждой темы.
- Для каждой темы
-
Распределение видеороликов по видеохостингам:
- Для каждой темы
j:- Вычислить базовое количество видеороликов на каждый видеохостинг:
q_j = C_j // K. - Определить количество видеороликов, которые нужно добавить дополнительно, чтобы минимизировать разницу:
r_j = C_j % K. - Распределить
q_jвидеороликов на каждый видеохостинг. - Для первых
r_jвидеохостингов добавить по одному дополнительному видеоролику этой темы.
- Вычислить базовое количество видеороликов на каждый видеохостинг:
- Для каждой темы
-
Вывод результата:
- Для каждого видеохостинга вывести количество загруженных видеороликов и их номера.
Реализация на Python:
import sys import math def main(): import sys import threading def solve(): import sys N, M, K = map(int, sys.stdin.readline().split()) t = list(map(int, sys.stdin.readline().split())) # Initialize theme to videos mapping theme_videos = [[] for _ in range(M+1)] for idx, theme in enumerate(t): theme_videos[theme].append(idx+1) # Video numbers are 1-based # Initialize K hosts hosts = [[] for _ in range(K)] for theme in range(1, M+1): videos = theme_videos[theme] C_j = len(videos) if C_j == 0: continue q_j = C_j // K r_j = C_j % K index = 0 for host_id in range(K): if q_j > 0: hosts[host_id].extend(videos[index:index+q_j]) index += q_j for host_id in range(r_j): hosts[host_id].append(videos[index]) index +=1 # Output for host in hosts: S = len(host) if S ==0: print(0) else: print(S, ' '.join(map(str, host))) threading.Thread(target=solve).start() if __name__ == "__main__": main()Пояснения к реализации:
-
Чтение входных данных:
- Считываются значения
N(количество видеороликов),M(количество тем) иK(количество видеохостингов). - Далее считывается список тем для каждого видеоролика.
- Считываются значения
-
Сборка списка видеороликов по темам:
- Создаётся список
theme_videos, где для каждой темы хранится список номеров видеороликов, относящихся к этой теме.
- Создаётся список
-
Распределение видеороликов:
- Для каждой темы вычисляется базовое количество видеороликов, которое должно быть загружено на каждый видеохостинг (
q_j), и количество видеороликов, которые нужно добавить дополнительно на первыеr_jвидеохостингов. - Видеоролики равномерно распределяются по всем видеохостингам с учётом дополнительных видеороликов для первых
r_jвидеохостингов.
- Для каждой темы вычисляется базовое количество видеороликов, которое должно быть загружено на каждый видеохостинг (
-
Вывод результатов:
- Для каждого видеохостинга выводится количество видеороликов, загруженных на него, и номера этих видеороликов.
- Если на видеохостинг не загружено ни одного видео, выводится просто
0.
Пример работы алгоритма:
Входные данные:
7 3 2 1 2 1 3 2 1 3Пояснение:
- Есть 7 видеороликов с темами: [1, 2, 1, 3, 2, 1, 3]
- Нужно распределить их по 2 видеохостингам.
Распределение:
- Тема 1: 3 видео → каждому хосту по 1 видео, оставшееся 1 видео добавляется первому хосту.
- Тема 2: 2 видео → каждому хосту по 1 видео.
- Тема 3: 2 видео → каждому хосту по 1 видео.
Выходные данные:
4 1 2 3 4 3 5 6 7- Первый хост получил видеоролики: 1, 2, 3, 4
- Второй хост получил видеоролики: 5, 6, 7
Заключение
Данный алгоритм обеспечивает равномерное распределение видеороликов по видеохостингам как в целом, так и по каждой теме отдельно, минимизируя разницу между количеством видеороликов на различных хостингах и по темам. Это позволяет Артёму получить наиболее сбалансированную статистику просмотров.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.