All submissions for this problem are available.
Some friends are going to a grand party. At the venue, there is a huge car parking lot with some empty spaces available. The parking spaces are located along a straight line at positions x1,...,xN. The friends have a weird idea of parking their cars. Instead of parking their cars close to each others, they decide to park their cars in such a way that the minimum distance between any of their two cars is as large as possible. What is the largest minimum distance?
- The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space separated integer N and K denoting the number of slots available and number of friends who have to park their cars.
- The next N line contains an integer denoting the available parking location, Xi.
For each test case output one integer: the largest minimum distance.
- 1 ≤ T ≤ 100
- 2 ≤ N ≤ 10^5
- 0 ≤ X ≤ 10^9
- 2 ≤ k ≤ N
Input: 1 6 3 2 5 8 7 1 3
Example case 1. They can park their vehicle at positions 1, 5 and 8 resulting in a minimum distance of 3.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 6.3, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.