## CCC '10 S3 - Firehose

View as PDF

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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### 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, 12: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, 12:26 a.m. edited

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Oct. 24, 2020, 8:59 p.m. edited

Can the length of the hoses contain decimals?

• commented on Dec. 3, 2020, 11:04 a.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. 9, 2017, 7:39 p.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.

• commented on Jan. 1, 2016, 9:36 p.m.

I feel like the judge doesn't give Java 7 the actual runtime.

• commented on Jan. 1, 2016, 10:32 p.m.

There exists some rare bug in the Java executor that causes a 0-second runtime. So far, only one other submission has demonstrated this bug. Thanks for producing another one!

• commented on Feb. 27, 2015, 7:40 p.m.

no it is not

• commented on Feb. 27, 2015, 8:07 p.m.

nvm ;)