COW


Submit solution

Points: 20
Time limit: 2.5s
Memory limit: 493M

Problem type

Anh nông dân Giang mới xây dựng một cái chuồng nuôi bò rất dài mới, với N (2 ≤ N ≤ 10 0000) gian. Các gian được xếp dọc theo một đường thẳng tại các vị trí x1, . . . , xN (0 ≤ xi ≤ 1000000000). C (2 ≤ C ≤ N) con bò của anh ta không thích cách bố trí chuồng nuôi này và trở nên hung hăng với nhau khi đưa vào cùng một gian chuồng. Để ngăn chặn các con bò làm tổn thương nhau, Giang muốn xếp các con bò vào các gian chuồng, sao cho khoảng cách tối thiểu giữa hai con càng lớn càng tốt.

Yêu cầu: Hãy giúp Giang tìm cách bố trí để có khoảng cách tối thiểu là lớn nhất.

Dữ liệu vào

Dòng đầu chứa một số nguyên t ≤ 30 là số lượng bộ test, tiếp theo mỗi bộ test có cấu trúc như sau:

• Dòng 1 chứa hai số nguyên cách nhau bởi dấu cách: N và C

• Dòng 2 . . . N + 1: Dòng i + 1 chứa một số nguyên, xi là vị trí của một ngăn chuồng.

Kết quả

Mỗi bộ test in ra trên một dòng một số nguyên là khoảng cách tối thiểu lớn nhất tìm được.

Sample Input

1
5 3
1
2
8
4
9

Sample Output

3

Giải thích

Giang có thể xếp 3 con bò của anh ta vào cách ngăn chuồng ở các vị trí 1,4 và 8, với khoảng cách tối thiểu thu được là 3.

Comments

There are no comments at the moment.