Canadian Computing Competition: 2010 Stage 1, Senior #3
There is a very unusual street in your neighbourhood. This street forms a perfect circle, and the circumference of the circle is . There are () 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 .
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 () 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.
The first line of input will be an integer , the number of houses. The next lines each contain one integer, which is the address of that particular house, and each house address is at least and less than . On the nd line is the number , 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 .
On one line, output the minimum integral length of hose required so that every house can connect to its nearest fire hydrant with that length of hose.
4 0 67000 68000 77000 2
Output for Sample Input