2010 Canadian Computing Competition, Stage 1

Problem 3: Firehose

There is a very unusual street in your neighbourhood. This street forms a perfect circle, and the circumference of the circle is 1,000,000. There are H (1 ≤ H ≤ 1000) houses on the street. The address of each house is the clockwise arc-length from the northern-most point of the circle. The address of the house at the northern-most point of the circle is 0.

You also have special firehoses which follow the curve of the street. However, you wish to keep the length of the longest hose you require to a minimum.

Your task is to place k (1 ≤ k ≤ 1000) fire hydrants on this street so that the maximum length of hose required to connect a house to a fire hydrant is as small as possible.

Input

The first line of input will be an integer H, the number of houses. The next H lines each contain one integer, which is the address of that particular house, and each house address is at least 0 and less than 1,000,000. On the H+2nd line is the number k, which is the number of fire hydrants that can be placed around the circle. Note that a fire hydrant can be placed at the same position as a house. You may assume that no two houses are at the same address. Note: at least 40% of the marks for this question have H ≤ 10. Also, the fire hydrants should be placed on integer locations.

Output

On one line, output the length of hose required so that every house can connect to its nearest fire hydrant with that length of hose.

Sample Input

4
0
67000
68000
77000
2

Sample Output

5000

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 23, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Will the house addresses always be given in ascending order?