После чудесного спасения из плена Бабы-яги, домовёнок Кузя оказывается в доме гимназистки Веры, которая в последнее время увлеклась живописью и рисованием. Чтобы помочь Вере в её занятиях, домовёнок решает приобрести для неё k k наборов карандашей. Каждый набор может состоять как из одного, так и из нескольких карандашей, и все они имеют положительную длину, выраженную целым числом миллиметров. image В художественной лавке на болоте Кикиморы можно найти n n различных наборов карандашей. После того как Кузя купит ровно k k наборов, он вернётся в дом Веры и сложит все карандаши в одну коробку. Гимназистка Вера будет очень рада, если разница в длине между наибольшим и наименьшим карандашами в этой коробке будет минимальной. Поэтому домовёнок просит вас о помощи: помогите ему выбрать из имеющихся n n наборов ровно k k так, чтобы разница между максимальным и минимальным среди всех купленных карандашей была как можно меньше. Формат ввода В первой строке вводятся два натуральных числа n n и k k ( 1 ≤ n ≤ 1 0 5 , 1 ≤ k ≤ n 1≤n≤10 5 ,1≤k≤n) – количество наборов карандашей в лавке Кикиморы и количество наборов, необходимое домовёнку Кузе. В каждой из следующих n n строк содержится c i c i ( 1 ≤ c i ≤ 2 ⋅ 1 0 5 1≤c i ≤2⋅10 5 ) — количество карандашей в наборе. Затем в той же строке идут c i c i натуральных чисел a i j a ij ( 1 ≤ a i j ≤ 1 0 9 1≤a ij ≤10 9 ) – длины карандашей в i i-м наборе. Гарантируется, что сумма всех c i c i не превышает 2 ⋅ 1 0 5 2⋅10 5 . Формат вывода В единственной строке выведите наименьшую разницу между максимальным и минимальным купленными карандашами, которую можно достичь.

Давайте подробно разберем задачу и подход к её решению. ### Постановка задачи: Есть `n` наборов карандашей, каждый набор — это один или несколько карандашей с целочисленной длиной. Нужно выбрать ровно `k` наборов так, чтобы разница между максимальной и минимальной длиной карандаша среди всех выбранных — была как можно меньше. Обзор шагов решения: 1. **Обработка входных данных**: - Вводим `n` и `k`. - Для каждого набора считаем минимальную и максимальную длину карандашей внутри него. - В итоге мы получим для каждого набора два числа: минимальную и максимальную длину. 2. **Преобразование данных**: - Для каждого набора определяем **минимальную длину** (`min_i`) и **максимальную длину** (`max_i`). - Создаем массив пар `(min_i, max_i)`. 3. **Перебор вариантов**: - Идея — упорядочить все наборы по их минимальной длине. - Тогда мы будем искать последовательность из `k` наборов подряд, для которых разница `max_i - min_i` минимальна. 4. **Поиск минимальной разницы**: - После сортировки по `min_i` перебираем все подряд идущие блоки длины `k`. - Для каждого блока определяем максимальную длину (`max_in_block`) и минимальную длину (`min_in_block`) в выбранных наборах. - Обновляем ответ, если разница `max_in_block - min_in_block` меньше текущего минимального. ### Почему так? - Отсортировать по `min_i` — помогает группировать наборы, которые имеют похожие минимальные значения карандашей. - Выбор `k` последовательных наборов по отсортированному массиву минимальных значений — это эффективный способ проверить все возможные комбинации. --- ### Реализация на Python: ```python n, k = map(int, input().split()) sets = [] for _ in range(n): data = list(map(int, input().split())) c = data[0] pencils = data[1:] min_length = min(pencils) max_length = max(pencils) sets.append((min_length, max_length)) # Сортируем по минимальной длине sets.sort(key=lambda x: x[0]) # Инициализируем переменную для хранения наименьшей разницы min_diff = float('inf') # Перебираем все последовательности длины k for i in range(n - k + 1): # Определяем максимальную и минимальную длину в выбранных наборах current_max = max(sets[j][1] for j in range(i, i + k)) current_min = min(sets[j][0] for j in range(i, i + k)) diff = current_max - current_min if diff < min_diff: min_diff = diff print(min_diff) ``` --- ### Итог: - Время выполнения — примерно `O(n log n)` из-за сортировки. - Важный момент — аккуратно выбрать `k` последовательных наборов после сортировки, так как это гарантирует проверку всех вариантов, которые могут дать минимальную разницу. Если есть дополнительные вопросы — спрашивайте!