Convicts in jail P81991
There are n jails beside a straight road. You know the position (in km) of each jail. Please choose the jails where to confine m dangerous convicts in order to maximize the minimum distance between two convicts.
For instance, consider five jails at positions 1, 10, 23, 42 and 50, and three convicts. Here, the optimum solution is to use the first, third and fifth jail, with a minimum distance of 22.
Input
Input consists of several cases, each with m and n, followed by the positions of the n jails. Assume 2 ≤ m ≤ n ≤ 104, and that the n positions are different and between 0 and 109.
Output
For every case, print the largest possible distance between the two nearest convicts.
Input
3 5 1 10 23 42 50 2 2 1000000000 0 4 6 4 0 2 5 3 1 3 6 4 0 2 5 3 1 2 6 4 0 2 5 3 1
Output
22 1000000000 1 2 5
- Author
- Javier Nistal
- Language
- English
- Official solutions
- C++
- User solutions
- C++