Входной файл: | Стандартный вход | Ограничение времени: | 2 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 1 |
В городе Плотноскане проходит научная конференция. Студенты местного университета были приглашены на конференцию в последний момент так, что они даже не успели подготовиться и прочитать программу конференции. Конференция проходит в большом зале в m-мерном пространстве. Слушатели собираются около докладчиков, образуя группы. Все члены группы либо имеют f ∈ N соседей на расстоянии не более ε (включая себя), либо находятся на расстоянии не более ε ∈ R от такого члена группы. При этом некоторые участники конференции не слушают доклады, витая в своих мыслях, и, таким образом, не принадлежат никакой из групп. Зная позиции всех участников в зале, помогите студентам определить количество участников в каждой группе, чтобы они могли выбрать наиболее интересные из них. Также, во избежание неопределённости было решено начинать поиск групп рассматривая участников в том порядке, в котором они указаны в списке.
При решении задачи разрешено использовать только стандартные библиотеки Python и библиотеку numpy.
Первая строка входного файла содержит числа n, m, ε, f — количество участников конференции, размерность пространства, внутреннее расстояние в группе и минимальное количество соседей. В следующих n строках содержится m вещественных чисел — координаты участников в пространстве.
Выходной файл должен содержать натуральные числа — количество участников в каждой группе, отсортированные в порядке возрастания.
50 ⩽ n ⩽ 2750
2 ⩽ m ⩽ 50
0.5 ⩽ ε ⩽ 25
3 ⩽ f ⩽ 15
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 | input.txt |
|