Реализуйте алгоритм k-means для одномерных данных (только координата x).
Для одномерных данных расстояние между точками вычисляется как модуль разности: |x₁ - x₂|
При равном расстоянии до нескольких центров точка присваивается кластеру с меньшим номером.
Формат входных данных
- Первая строка: два целых числа n и k (1 ≤ k ≤ n ≤ 1000) — количество точек и кластеров
- Вторая строка: n целых чисел через пробел — значения точек (−10⁶ ≤ xᵢ ≤ 10⁶)
- Третья строка: k вещественных чисел через пробел — начальные центры кластеров
Формат выходных данных
- Первая строка: k вещественных чисел — финальные центры кластеров (округлённые до 1 знака после запятой)
- Вторая строка: n целых чисел — номер кластера (0-индексация) для каждой точки в порядке их появления во входных данных
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 2
15 16 14 30 32 31 15 29 33 16
15 30
|
15.2 31.0
0 0 0 1 1 1 0 1 1 0
|