Woburn Challenge 1996
Problem 1: Fishes in a Tank
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 is 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 n by n by n cube and hence in the eclipsed configuration it will have at most n^2 groups as it has only n^2 separate vetical columns. You are to find the level (or depth) at which there there is the largest number of fishies. The top level of the tank is level 1, and the bottom level of the tank is level n. If mutliple levels each have the most number of fish, give the topmost of these levels.
For exmaple, consider the a 3x3x3 cube with a group of 3 fish on the center vertical column, and two single fish in opposite corners. If we label the columns with co-ordinates from (1, 1) to (3, 3) this could be described as:
- In column (2, 2): A stack of fish from level 1 to level 3
- In column (1, 1): A stack of fish from level 1 to level 1 (i.e. only in level 1)
- In column (3, 3): 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
In the data file there are 5 data sets. The first line of each data set is n (1 ≤ n ≤ 50), the size of the cubic fishtank to be considered. The next lines each contain four integers (x, y, t, b) which indicate a column of fish at (x, y) whose top fish is in level t and whose bottom fish is in level b. (And of course there are fish at each level t+1, t+2 ... b 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
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
All Submissions
Best Solutions
Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
3
2 2 1 3
1 1 1 1
3 3 3 3
0 0 0 0
It doesn't matter much as it's still understandable. It just matters for the sake of continuity...