Тот самый Артём из одной из предыдущих задач рассказал Юре про необычный способ разбиения видеороликов и тем по видеохостингам. Юра не смог толком понять общее правило разбиения и…
Тот самый Артём из одной из предыдущих задач рассказал Юре про необычный способ разбиения видеороликов и тем по видеохостингам. Юра не смог толком понять общее правило разбиения и решил задать Артёму несколько вопросов с конкретными примерами разбиений видеозаписей. Для каждого примера Артём должен ответить, является ли он корректным или нет. Так Юра надеется понять общее правило из частных примеров. Утомившись от однообразия вопросов, Артём решил автоматизировать свои ответы. Максимум баллов за задачу - 100. Формат входных данных Первая строка содержит одно натуральное число Q ( 1 ≤ Q ≤ 10 ) — число вопросов, которые задаст Юра. Далее следуют Q вопросов. Каждый вопрос начинается со строки, которая содержит три натуральных числа N , M , K ( 1 ≤ N ≤ 10 5 , 1 ≤ M , K ≤ N ) — число видеороликов, тем и видеохостингов. Все они пронумерованы с единицы. Вторая строка вопроса содержит N натуральных чисел t i ( 1 ≤ t i ≤ M ) — тема i -го видеоролика. Далее следует K строк, которые описывают разбиение. Каждая строка начинается с целого неотрицательного числа S — числа видеороликов, загруженных на соответствующий видеохостинг. Далее в той же строке идут S не превышающих N натуральных чисел — номера соответствующих видеороликов. Гарантируется, что сумма S по всем вопросам и видеохостингам и сумма K по всем вопросам не превышают 10 5 . Формат выходных данных Выведите Q строк, каждая из которых должна содержать «YES», если соответствующие разбиение корректно, и «NO» иначе. Пример 1 Входные данные 2 10 4 3 1 2 2 3 3 3 4 4 4 4 4 1 2 4 8 3 7 3 5 3 9 6 10 10 4 3 1 2 2 3 3 3 4 4 4 4 4 1 2 3 4 3 5 6 7 3 8 9 10 Выходные данные YES NO
Давайте разберёмся с задачей и разложим её по шагам, чтобы понять логику проверки корректности разбиений видеороликов.
Условия задачи (обобщённо):
- Есть
Nвидеороликов, каждый относится к определённой теме. - Есть
Kвидеохостингов, на каждом из них размещён некоторый набор видеороликов. - Необходимо определить, соответствует ли такое разбиение видеороликов по видеохостингам правилу, заданному Артёмом.
Основные идеи проверки:
Что считается корректным разбиением?
Без явного описания правила, из примеров и логики можно сделать предположение:
- Может быть проблема в том, что видеоролики, принадлежащие одной теме, должны размещаться на одном и том же видеохостинге или не разбиваться между разными хостингами.
Посмотрим на примеры:
Пример 1:
Тема роликов: [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
Разбиение:
- Хостинг 1: 1, 2, 4, 8
- Хостинг 2: 3, 7, 3, 5
- Хостинг 3: 9, 6, 10
Проверим, к примеру, тему 1 — её ролик №1 размещён только на хостинге 1, и тема 2 — её ролики (2, 3, 4) — тоже все в одном или разбросаны?
В основном, для видеороликов одинаковой темы, все они должны размещаться на одном видеохостинге, иначе правило нарушается.
Итоговая гипотеза:
Правило: все видеоролики одной темы должны находиться на одном видеохостинге, то есть Каждая тема должна полностью быть размещена только на одном видеохостинге.
Если это условие выполняется, ответ "YES", иначе — "NO".
Как проверить?
Создать отображение темы в видеохостинг, на котором расположены все ролики этой темы.
Проверить, чтобы все ролики одной темы находились на одном видеохостинге.
Если для любой темы ролики разбросаны по разным видеохостингам, возвращается "NO".
Пошаговое решение (алгоритм):
Чтение данных: количество вопросов, далее для каждого вопроса:
Построение массива тем для каждого видеоролика.
Построение словаря: тема -> видеохостинг, где размещаются ролики.
Для каждого видеоролика:
- Определяем тему.
- Запоминаем, на каком видеохостинге он размещён.
Для каждой темы проверяем, все её видеоролики располагаются на одном видеохостинге.
- Если да — продолжить.
- Если нет — вернуть "NO".
По завершении проверки — ответ "YES".
Реализация кода (на Python):
Q = int(input()) # число вопросов
for _ in range(Q):
N, M, K = map(int, input().split())
topics = list(map(int, input().split())) # темы видеороликов
# Создаем словарь: тема -> видеохостинг
theme_hosting = {}
valid = True
# Для каждого видеохостинга:
hostings = []
for _k in range(K):
data = list(map(int, input().split()))
S = data[0]
videos = data[1:]
hostings.append(videos)
# Проверяем для каждого видео
for v in videos:
theme = topics[v - 1] # тема видеоролика v
if theme not in theme_hosting:
theme_hosting[theme] = v # запоминаем хостинг, где размещён первый ролик этой темы
else:
# Проверяем, что все ролики этой темы на одном и том же хостинге
if theme_hosting[theme] != v:
valid = False # нашли ролик той же темы, но на другом хостинге
break
if not valid:
break
print("YES" if valid else "NO")
Итог:
- Программа проверяет, что все видеоролики каждой темы размещены на одном и том же видеохостинге.
- Если условие нарушается — ответ "NO".
- В противном случае — "YES".
Если есть ещё вопросы или нужно более подробно разобрать код — скажите!
