Задачі
Морозиво
Морозиво
Вздовж моря вузькою полоскою тягнеться пляж. У деяких точках пляжу розміщено кіоски з морозивом. В один прекрасний день не усі морозивщики вийшли на роботу. Розподіліть морозивщиків по кіоскам так, щоб мінімальна відстань між морозивщиками було якомога більшою. Так вони менше будуть заважати один одному.
Вхідні дані
У першому рядку вводяться кількість кіосків n
(2 ≤ n
≤ 10001) та кількість морозивщиків k
(1 ≤ k
≤ n
), які вийшли на роботу. У другому рядку задано n
натуральних чисел у порядку зростання - координати кіосків (координати не перевищують 109
).
Вихідні дані
Виведіть одне число - мінімальну відстань між сусідніми кіосками в оптимальному розміщенні.
Вхідні дані #1
5 3 1 2 3 100 1000
Вихідні дані #1
99
Вхідні дані #2
8 4 2 7 10 15 18 22 25 27
Вихідні дані #2
8