Programmer, Rank Thyself
Time limit1sMemory limit128 MB
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 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 (), the number of teams in the contest. The next 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 ; a time of means the corresponding problem was not solved.
Teams are ranked by the following criteria, applied in order:
- greatest number of problems solved (a problem is solved when its time is nonzero);
- then least total time (the sum of all seven times);
- 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 . Otherwise, if the nonzero times are , the geometric mean is
where and is the natural logarithm. Use exactly this definition. After computing the geometric mean, round it to an integer by adding and truncating the fractional part.
Output
For each contest, print a header line CONTEST k, where is the contest number starting from . 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.