Một công ty viễn thông muốn xây dựng trạm BTS dọc theo một con đường dài km. Vị trí tiềm năng để xây dựng trạm BTS được đánh dấu bằng các số nguyên . Công ty muốn khoảng cách tối thiểu giữa hai trạm BTS bất kỳ là lớn nhất có thể. Hãy tìm khoảng cách tối thiểu lớn nhất đó.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và ().
Dòng thứ hai chứa số nguyên ().
Kết quả: In ra một số nguyên duy nhất là khoảng cách tối thiểu lớn nhất giữa hai trạm BTS.
Ví dụ:
Dữ liệu:
5 3
1 2 4 8 9
Kết quả:
3
Giải thích:
Chọn các vị trí 1, 4, 8. Khoảng cách nhỏ nhất là 3.
Chọn các vị trí 1, 4, 9. Khoảng cách nhỏ nhất là 3.
Chọn các vị trí 1, 8, 9. Khoảng cách nhỏ nhất là 1.
Chọn các vị trí 2, 4, 8. Khoảng cách nhỏ nhất là 2.
