Not an official ACM page
[Problem 3 | 1996 East-Central problem set | My ACM problem archive | my home page]

ACM East Central Region
1996 Regional Programming Contest

Problem 2 - Supercomputer Selection, The Sequel

Valentine sighed as she sat down to lunch with her cousin, Martin Thiel, in the BIT student union Diner.

"What's the matter, Valentine?" Martin asked.

"My presentation to the SSC. They all really liked the graphical displays of the criteria and the selection process," Valentine grudgingly admitted. "But, Prof. Everett pointed out that the criteria would change over time and since we will be using the machine over several years, that we needed to take that into account as well."

"Maybe you could make separate graphs for each year?" suggested Martin.

"That's what I said to Prof. Everett, but she didn't think that would be sufficient --- it would only pick the best machine for a particular year."

As Valentine silently pondered her problem, Jake Briggs, one of Valentine's CS classmates, joined Martin and Valentine at their table. "What's up?" he asked. Valentine explained her dilemma.

"Simple," Jake mumbled through bites of his club sandwich. "Make three-dimensional shapes, using time as the third axis. The computer with the largest volume wins."

Valentine sketched out a perspective drawing of such a volume as well as a detail of a single quadrant. "What do we do here at the edges of the axes? There are four points." Valentine pointed to the points a, b, c, and d in her drawing of the quadrant.

"Just use two planes, one determined by a, b, and c, and the other determined by b, and c, and d."

"Whoa! Problem!" exclaimed Martin. "Those volume things are way too complicated for slideware. You'll just confuse everyone."

"No problem," Jake said. "We can use our virtual reality cave over in the JFK building. It even has tactile feedback gloves. The committee members can touch the volumes if they want."


The first line of input will contain two integers. The first integer, n, specifies the number of criteria that will be measured for each year. This value will be such that 1 <= n <= 100. The second integer, y specifies how many years will be considered. The value of y will be such that 1 <= y <= 10.

The rest of the input will consist of sequences of possible configurations of supercomputers; each line will contain n floating point values. The supercomputer configurations will be grouped in sets of y, i.e., the first y lines (after the initial line of two integers) will be the yearly configurations for the first computer. The next y lines will be the yearly configurations for the second computer, etc.

The first number on the input line corresponds to the value on the first axis, the second number corresponds to the value on the second axis, and so on.

The final line of input will contain n floating point zeros.


The output should be the configuration number (indexed from 1) which gives the configuration with the greatest volume, along with the value of the volume. The volume is to be given to two decimal places. Assume that the polygons are spaced with unit time along the time axis.

In case of a tie (i.e., multiple configurations are given that produce a polygon of equal volume), output the one with the lowest configuration number.

Sample Input

5 2 
1.2 2.3 3.4 4.5 5.6 
0.2 3.3 4.4 5.6 4.5 
10.0 11.0 12.0 13.0 14.0 
9.0 12.0 11.0 14.0 13.0 
0.0 0.0 0.0 0.0 0.0 

Output for the Sample Input

2 339.84 

Judge's Data

Set 1 input, output
This page maintained by Ed Karrels.
Last updated November 25, 1997