Programmer, Rank Thyself

Time limit1sMemory limit128 MB

Summary
Rank teams by problems solved, total time, and rounded geometric mean, then print aligned result tables.
Level

Medium4 of 10

Topics
Sorting, Math, Simulation, Implementation
Solved
No attempts yet

Problem

Implement a ranking program for a programming contest.

Each team solves up to seven problems. For every team you are given the time at which each problem was solved; a time of 00 means the problem was not solved. Your job is to rank the teams and print a formatted results table for each contest.

Input

The input contains one or more contests, followed by a line containing only a single 0 that marks the end of the input.

Each contest begins with a line containing a positive integer cc (1≤c≤201 \le c \le 20), the number of teams in the contest. The next cc lines each contain a team name followed by the solution times for the seven problems, all separated by spaces. A team name is between one and ten letters long, and all team names within a contest are distinct. Every time is a nonnegative integer no greater than 500500; a time of 00 means the corresponding problem was not solved.

Teams are ranked by the following criteria, applied in order:

  1. greatest number of problems solved (a problem is solved when its time is nonzero);
  2. then least total time (the sum of all seven times);
  3. then least geometric mean of the nonzero times (after rounding, described below).

Teams that are equal on all three criteria are tied: they share the same numeric rank and are listed in alphabetical order using a case-sensitive comparison. The numeric rank of a team is always one more than the number of teams ranked strictly ahead of it (teams tied with it are not counted).

The geometric mean is rounded to an integer, and only this rounded value is used both for ranking and for display. If all seven times are zero, the geometric mean is 00. Otherwise, if the nonzero times are t1,t2,…,tnt_1, t_2, \ldots, t_n, the geometric mean is

exp⁡ ⁣(ln⁡t1+ln⁡t2+⋯+ln⁡tnn)\exp\!\left(\frac{\ln t_1 + \ln t_2 + \cdots + \ln t_n}{n}\right)

where exp⁡x=ex\exp x = e^x and ln⁡x\ln x is the natural logarithm. Use exactly this definition. After computing the geometric mean, round it to an integer by adding 0.50.5 and truncating the fractional part.

Output

For each contest, print a header line CONTEST k, where kk is the contest number starting from 11. The header is followed by one line per team, in ranked order.

Each team line lists, separated by spaces: the rank, the team name, the number of problems solved, the total time, the rounded geometric mean, and then the seven individual solution times in the same order they appeared in the input.

All lines in the output share the same column widths, computed once over the entire input (across every contest, not per contest). For each column the width is the largest width needed by any value in that column anywhere in the input; pad narrower values with spaces (never tabs) to that width. The team name is left-justified; every other field is right-justified. The rank always occupies two digits, with a leading zero when necessary. The seven time columns share a single common width. No line begins or ends with a space.

Examples1

  1. Example 1

    Input
    1
    Plutonians 123 234 345 456 167 278 389
    4
    Xap 0 0 0 0 0 0 0
    Foo 20 30 0 50 40 0 10
    Bar 0 50 20 0 10 40 30
    Baz 0 0 0 0 0 0 0
    3
    Venus 213 0 0 57 0 0 0
    Neptune 0 0 0 117 153 0 0
    Mars 0 150 0 0 0 0 120
    0
    
    Expected output
    CONTEST 1
    01 Plutonians 7 1992 261 123 234 345 456 167 278 389
    CONTEST 2
    01 Bar        5  150  26   0  50  20   0  10  40  30
    01 Foo        5  150  26  20  30   0  50  40   0  10
    03 Baz        0    0   0   0   0   0   0   0   0   0
    03 Xap        0    0   0   0   0   0   0   0   0   0
    CONTEST 3
    01 Venus      2  270 110 213   0   0  57   0   0   0
    02 Mars       2  270 134   0 150   0   0   0   0 120
    02 Neptune    2  270 134   0   0   0 117 153   0   0