## CCC '10 S3 - Firehose

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types
##### 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.

#### Input Specification

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 .

#### Output Specification

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.

#### Sample Input

4
0
67000
68000
77000
2

#### Output for Sample Input

5000

• commented on Jan. 2, 2021, 5:08 a.m.

The problem does not specify whether the location of each fire hydrant has to be an integer and whether the length of the hoses can contain a decimal. This should be added to the question as some of the solutions are different if you assume that the lengths and positions are not limited to integers.

• commented on Dec. 24, 2020, 5:26 a.m. edited

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on Oct. 25, 2020, 12:59 a.m. edited

Can the length of the hoses contain decimals?

• commented on Dec. 3, 2020, 4:04 p.m.

I think it can be shown that the only decimal will be point 5, in which case I think you just round up.

• commented on Feb. 10, 2017, 12:39 a.m.

The original CEMC test data is now worth 80% of the marks. New cases, worth the remaining 20%, have been added.

All submissions have been rejudged.