CCC '10 S3 - Firehose

View as PDF
Submit solution
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 1000000. 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 Specification

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 1000000. 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.

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

Copy
4
0
67000
68000
77000
2

Output for Sample Input

Copy
5000

Comments


  • 0
    khanhbber11  commented on Aug. 13, 2024, 4:02 a.m.

    idk but why H is so small, (brute force pass?).I think H should be (H<=1e5), i pass this problem with O(h.log(1e6))


  • 14
    BalintR  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.


  • -21
    Ch4rIes  commented on Dec. 24, 2020, 5:26 a.m. ← edited

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


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

    Can the length of the hoses contain decimals?


    • 5
      ross_cleary  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.


  • 3
    Phoenix1369  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.