Problem 103: Islands in the Pond
(U.M. ACM Runoffs 2001, problem 3)
Description
An annoying little kid in the tradition of programming contest problems,
let's call him Joey, has been piling up concrete blocks in an empty pond.
Each of the blocks are 2 feet wide and 1 foot high; they are laid down
in a single row in perfectly aligned piles. Each pile may be of any height
(so long as it is an exact number of feet of course) except that no pile
will be empty. Every pile will fit snugly up against its neighbours, so the
row of blocks is always an exact multiple of 2 feet long.
Once Joey has piled up the concrete blocks, he will pour some water into the
pond. This will result in the row of blocks being split up into a number
of islands, separated by a flooded area, just as in the diagram above.
Joey wants to know what the length of the longest individual island will be,
and you must write a program to work it out.
The diagram shows an instance of this problem in which there are 10 piles
of blocks, the number of blocks in each pile are (1, 3, 2, 3, 4, 6, 5, 4, 2, 7)
and the water is 2.52 feet deep. As you can see, the largest island is
10 feet wide.
The input to the program will consist of a number of test cases, each
providing the number of piles of blocks in the row, and the number of blocks
in each pile, and the depth to which the pond is filled.
Input Format
Each test case will occupy three lines of input, there could be any number of
test cases.
The first line of each test case contains a single integer, N, which is the
of piles of blocks in the row. When N=0 that signals the end of the input.
The next line contains N integers, specifying the number of blocks in
each pile, traversing the row from left to right.
The third line of each case contains a single floating point number, D, specifying
the depth in feet of water to be poured into the pond.
Output Format
For each test case, you should print one line of output, containing the
text "Test case NNN: The biggest island is XXX feet wide.", with NNN
replaced by the test case number (starting from 1) and
XXX replaced by the actual
width as an integer in decimal. If all the blocks are under water
print "Test case NNN: All flooded." instead.
Limits
For each test case, the number N will be positive and less than 100,000.
D will never
be an exact integer, so you do not have to worry about what to do when the
depth of water exactly equals the height of one of the piles.
Sample Input
10
1 3 2 3 4 6 5 4 2 7
2.52
4
5 6 7 8
3.1
3
1 2 1
193.17
0
Sample Output
Test case 1: The biggest island is 10 feet wide.
Test case 2: The biggest island is 8 feet wide.
Test case 3: All flooded.
End of Problem