Woburn Challenge 1996
In a cubic fish tank, some fishes are swimming around. Little Billy-Bob watched the fishes move around and around until he became dizzy. At some time during the day, the fishes were all stacked together in one column, at other times they were scattered randomly in the tank and at still other times they were in an eclipsed configuration. It was this configuration that Billy-Bob enjoyed watching the most.
In this eclipsed configuration, the fishes were grouped together in vertical columns of varying length, and in each group the fishes are one on top of another. Never were there two or more groups in the same vertical column, though. Thus the tank looked like it had chains of fish hanging vertically.
Little Billy-Bob would try to figure out which level (or depth) in the tank had the most number of fishes when it was in this configuration. But he had to do it fast before the fishes moved past one another and ruined all his fun.
You can help Billy-Bob by writing a program that does the work for him.
The fish tank will be an cube and hence in the eclipsed
configuration it will have at most
groups as it has only
separate vertical columns. You are to find the level (or depth) at which
there is the largest number of fishes. The top level of the tank
is level 1, and the bottom level of the tank is level
. If multiple
levels each have the most number of fish, give the topmost of these
levels.
For example, consider a cube with a group of 3 fish on the
center vertical column, and two single fish on opposite corners. If we
label the columns with co-ordinates from
to
this could be
described as:
- In column
: A stack of fish from level 1 to level 3
- In column
: A stack of fish from level 1 to level 1 (i.e. only in level 1)
- In column
: A stack of fish from level 3 to level 3 (i.e. only in level 3)
In this case, there are two fish each at levels 1 and 3, so we give the topmost (1).
Input Specification
In the data file, there are 5 data sets. The first line of each data set
is
, the size of the cubic fishtank to be
considered. The next lines each contain four integers
which
indicate a column of fish at
whose top fish is in level
and
whose bottom fish is in level
. (And of course, there are fish at each
level
since Billy only likes these particular fish-stack
configurations as mentioned above). This set of fish-columns is
terminated by a line containing all zeroes.
Output Specification
Give the topmost level of all those containing the biggest number of fish.
Sample Input
3
1 1 3 3
2 2 1 3
3 3 1 1
0 0 0 0
(and 4 more data sets)
Sample Output
1
Comments