Однажды один рассеянный профессор дал задание студентам: произвести выборку без повторений случайного непустого подмножества объектов из набора данных. Результат выполнения задания — список номеров объектов. Он собрал эти списки у студентов и нечаянно объединил их в один большой список. Теперь профессор не может проверить отдельно список каждого студента. Тогда он решает, что просто попробует подобрать такие списки, которые в итоге дадут один большой полученный список. Если такие списки существуют, всем студентам зачтётся выполнение задания. Если нет — не зачтётся никому. Помогите профессору определить, существуют ли такие списки? Замечание В первом подтесте примера студенты могли в качестве ответа дать профессору списки: [1, 2, 3], [2, 3] и [3]. Система оценки Всего в задаче 32 теста (не считая примера). Первые 28 тестов оцениваются в 3 балла. Следующие 4 теста оцениваются в 4 балла. Формат входных данных Каждый тест состоит из нескольких подтестов. Первая строка содержит натуральное число Q (1 ≤ Q ≤ 105) — число подтестов. Далее идёт описание подтестов. Каждый подтест задаётся двумя строками. Первая из них содержит три разделённых пробелами натуральных числа N, M и K (1 ≤ N, M, K ≤ 105): N — длинна полученного после объединения списка номеров объектов, M — число объектов в исходном наборе данных, K — число студентов. Объекты в наборе данных пронумерованы от 1 до M. Вторая строка каждого подтеста содержит описание большого списка объектов и состоит из N разделённых пробелами натуральных чисел ai (1 ≤ ai ≤ 105) — номеров объектов. Сумма N по всем подтестам одного теста не превышает 105. Формат выходных данных Для каждого теста выведете строку YES, если студентам следует зачесть задание, или NO в противном случае. Пример 1 Входные данные 2 6 3 3 1 2 3 2 3 3 6 3 3 1 2 3 2 3 4 Выходные данные YES NO

Давайте разберемся с условием задачи и решим ее пошагово. --- ## Условие задачи (подробное объяснение) есть несколько подтестов, для каждого из них даны: - **N** — длина объединенного списка объектов, полученного студентами. - **M** — количество объектов в исходном наборе (нумерация объектов от 1 до M). - **K** — число студентов. На входе — длинный список из N элементов, каждый из которых — номер объекта из множества 1..M. Этот список — объединение списков, которые студенты могли подготовить, выбирая непустые подмножества объектов (без повторений внутри каждого подмножества). Пусть каждый студент выбрал своё непустое подмножество, и их объединение дает итоговый список. Задача: определить, существует ли набор таких подмножеств (по одному для каждого студента), что объединение их элементов дает исходный объединенный список без пропусков и лишних элементов. То есть, можно ли разбить исходный список на K частей так, чтобы каждая часть — непустое подмножество, и объединение всех этих частей — первоначальный список. Если да, нужно вывести **YES**, иначе — **NO**. --- ## Что нужно понять и проверить? - В исходном списке `a` каждый элемент может встречаться несколько раз. - Эти повторения можно "распределить" по студентам так, чтобы каждое студенческое подмножество было непустым, и сумма всех этих подмножеств дала исходный список. - Важное ограничение: каждый элемент может принадлежать только одному студенту, потому что списки студентов — не пересекаются внутри, но могут пересекаться по одинаковым объектам? В условии указано, что "выборка без повторений", так что внутри одного подмножества — уникальные элементы. В списке после объединения эти подмножества «склеены» вместе, и элементы могут повторяться. --- ## Основное правило: - Для каждого уникального номера объекта из `a`, ему соответствуют несколько вхождений. - Эти вхождения нужно "распределить" по разным студентам, так чтобы у каждого студента было хотя бы одно вхождение этого объекта, если он есть в списке. ## Ключевой момент: - Чтобы представить исходный список как объединение непустых подмножеств — у каждого уникального элемента в списке `a` должно быть не меньше, чем число его встреч: `count[a_i]`. - Если количество встреч одного элемента больше K — это невозможно, потому что в каждой группе (подмножестве студента) он может быть только один. Тогда есть смысл, что каждый студент может взять этот объект только один раз, и total count[a_i] должно быть не больше K, иначе нельзя распределить его по студентам. Но так как элементы могут встречаться несколько раз, и мы не знаем, как именно студенты собирали свои списки (они могли выбрать один и тот же объект, и его встречается много — в этом случае нужно понять, можно ли так разбить). --- ## Обоснование и решение: - Для каждого элемента `x` подсчитаем количество вхождений `count[x]`. - Если существует какой-то `x`, для которого `count[x] > K`, значит один студент не сможет "включить" все встречающиеся `x` в свой список, а остальные студенты — нет, значит, ответ **NO**. - Иначе, ответ **YES**. --- ## Пошаговое решение: 1. Прочитать количество подтестов. 2. Для каждого подтеста: - Прочитать N, M, K. - Прочитать список `a`. - Подсчитать частоты появления каждого уникального элемента. - Проверить, есть ли элемент `x`, у которого `count[x] > K`. - Если есть — выводим **NO**. - Иначе — **YES**. Это — достаточно эффективный и логичный способ проверки. --- ## Реализация на Python: ```python Q = int(input()) for _ in range(Q): N, M, K = map(int, input().split()) a = list(map(int, input().split())) # Подсчет частот freq = {} for num in a: freq[num] = freq.get(num, 0) + 1 # Проверка ограничений answer = "YES" for count in freq.values(): if count > K: answer = "NO" break print(answer) ``` --- ## Итог: - Если у какого-либо числа количество встреч больше K, то распределить его невозможно → **NO**. - Иначе возможно → **YES**. Этот подход работает за O(N) — достаточно беглого подсчета частот. --- Если нужны дополнительные разъяснения или пример, я с радостью помогу!