During the Fall of 2011, all of the high-school-senior cows are making their visits to various colleges and universities. When they arrive at Harvey Mudd, the cows are most interested in the availability of coffee throughout the campus.
Dean Jacobsen, hoping to lure the whole herd to HMC, has offered to scuttle the new academic building project and, in its place, to build coffee shops across campus for the cows. Specifically, Dean Jakes would like to know where he should place these cafes -- and how much moovement will still be required for the cows to get to their java.
The cows enjoy herding and they know they will create a number of "cow-preferred hang outs" at HMC. However, the exact locations of those hang-outs will depend on factors like the weather and their proximity to CS classes. Thus, for a given set of "preferred hang outs" and a given number of available coffee kiosks, Jakes would like to know how well-coffee'd the cows will be.
The plan is to place the available kiosks so that the maximum distance between any hang-out spot and its nearest kiosk is as small as possible. For the purposes of the cows' caffeination, HMC's campus can be considered a one-dimensional strip, whose origin is the western edge, Olin, where the CS department is located. Each location to the east of Olin is measured in millimeters, and only integer locations are considered.
1 2 3 1 3 10
This indicates 1 test case, two coffee kiosks, and 3 hang-out locations at 1mm, 3mm, and 10mm east of Olin, respectively. The cows move slowly, so they like their herding spots close together!
Dean Jakes can build the two kiosks at location 2 and location 10. In this case the greatest coffee-distance would be 1.0, namely the distance from 1 to 2 (and it's also the distance from 3 to 2).
Hint: try binary search!