1999 Canadian Computing Competition, Stage 2
Day 2, Problem 3: Fast Food
The fast food chain, McBurger, has recently consolidated all activities to restaurants along the Trans Canada Highway. (Following the completion of fixed links joining Newfoundland and Vancouver Island to the mainland.) They have also decided to build several warehouses along the highway, each located at a restaurant and supplying those restaurants nearby. Naturally, these warehouses should be placed so as to minimize the distance between the warehouses and the restaurants they service. Your task is to write a program that determines the optimal positions for the warehouses.
To make the problem more precise, chairman McBoss has issued the following specification: You are given the positions of n restaurants across the country as n integers d1 < d2 < ... < dn. These integers are the distances, in kilometres, from the company's new headquarters in St. John's, at the extreme Eastern end of the highway. You are also given the number k ≤ n, the number of warehouses to be constructed. You are to place the warehouses at the locations of k of the n restaurants so as to minimize the maximum distance from any restaurant to its nearest warehouse.
Input
The input file contains several test data sets. Each data set begins with the two integers n ≤ 200 and k. Following this will be n non-negative integers d1, d2, ... dn, none of which exceeds one million. The number 0 will follow the last data set. Each integer will be on a separate line of input.Output
For each input data set, output three lines. The first line must contain k integers giving the locations of the warehouses, in kilometres from head office, in ascending order. If several sets of warehouse locations yield the same maximal distance, any one will do. The second line must contain the maximum distance from any restaurant to the nearest warehouse (this is the quantity that your program is to minimize). The third line must be blank.Sample Input
6 3 5 6 12 19 20 27 0
Sample Output
6 20 27 6
All Submissions
Best Solutions
Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 19, 2009
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
9 23 24
4
You can only use restaurant locations.