tank problem

[sara khan]

PROBLEM 4 - WATER TANKS
There are n identical large cylindrical tanks for storing water. The tanks are arranged
in a circle on level ground. Each tank is connected with its two neighbours by means
of pipes situated at its base. There is a valve between each adjacent pair of tanks
(tank n is next to tank 1). All valves are initially closed. All the outlets and the pipes
are at the same level and are always full of water, even if all the tanks are deemed to
be “empty”.
The volume in any tank is measured by the height of the surface of the water above
the level of the top of the outlets. If all valves (or all valves but one) are opened so
that water can flow between the tanks, then the levels will eventually equalise.
Conversely, if all tanks are initially at the same level, no valves need be opened to
equalise the levels. Thus it may be necessary to only open some of the valves to
achieve this result.
For example, consider n=4 tanks each 5 metres high. Assume that the water level in
these tanks is at 4, 4, 3, and 3 meters respectively. Their water level will equalise if
we open the valves between tanks #2 and #3 and between #4 and #1, as suggested
by the following diagram. Thus for this set we need to open only two valves:
Given a set of initial heights, determine the minimum number of valves to open so
that the final water levels in all tanks is equal.
closed open closed open
to #4 to #1
#1 #2 #3 #4
P4 - ACM SPPC 2 of 2 Saturday, 20/09/2003
INPUT FORMAT 1
The input will consist of one or more scenarios, each scenario consisting of two lines.
The first line contains a descriptive title, which is a string of letters or spaces no more
than 200 characters long, containing at least 1 letter.
The second line starts with the number of basins n (3 £ n £ 200), a space, and then n
integers in the range 0 to 99, separated by single spaces, representing the water
levels in the tanks.
The scenarios sequence is terminated by a single ‘#’ character on a line by itself.
SAMPLE INPUT:
High four dude basins
4 4 4 3 3
The Australasian eight
8 2 1 1 2 2 1 1 6
#
OUTPUT FORMAT
Output one line for each input scenario. The line consists of the first letter of each
word in the descriptive title in upper case, followed by a colon (‘:’), a space, and then
the minimum number of valves that need to be open to achieve equal heights in all
tanks.
SAMPLE OUTPUT:
HFDB: 2
TAE: 5

if anyone understand how the output is generated then please tell me...