### 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)

Danielon Mar 20, 2011 - 12:00:59 am UTC Wait...9 23 24

4

SourSpinachon Mar 20, 2011 - 1:22:27 am UTC Re: Wait...You can only use restaurant locations.