POJ 1245

Programmer, Rank Thyself

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 1174		Accepted: 448

Description

Implement a ranking program similar to the one used for this programming contest.

Input

The input file contains one or more contests followed by a line containing only zero that signals the end of the file. Each contest begins with a line containing a positive integer c no greater than 20 indicating the number of teams in the contest, and is followed by c lines that contain a team name and the solution times for seven problems, separated by spaces. Team names consist of between one and ten letters. All team names within a contest are unique. Times are nonnegative integers no greater than 500.

As described in the Notes to Teams, teams are ranked first by greatest number of problems solved, then by least total time, then by least geometric mean of all nonzero times. Teams that are still tied are given the same numeric ranking and are listed in alphabetical order, using case-sensitive string comparison. The numeric ranking for a team is always one more than the number of teams ranked ahead of (not tied with) that team. For this problem all geometric means will be rounded to an integer as described below, and only the rounded value will be used when computing rankings and displaying results.

If all times are zero, then the geometric mean is also zero. Otherwise, if there are n nonzero times t1, ..., tn, then the geometric mean is defined to be

exp ((ln t1 + ln t2 + ... + ln tn) / n)

where exp x means e^x and ln x means the natural logarithm of x. (There are other mathematically equivalent definitions of the geometric mean, but they may produce slightly different answers due to roundoff and/or overflow problems. Use this definition to get the same answers as the judges.) After computing the geometric mean, round it to an integer by adding 0.5 and truncating any fractional digits. (C/C++ and Java automatically truncate fractions when casting a floating-point type to an integral type. In Pascal use the trunc function.)

Output

For each contest you must output the rankings in a table. All tables will have the same width, with the length equal to the number of teams entered in the contest. Use the exact format shown in the examples. Each contest has a numbered header followed by a table with one team entry per line. Each entry contains the ranking, team name, problems solved, total time, geometric mean, and then the individual solution times in the same order they appeared in the input. In the first example all values completely fill their fields. In general you may need to pad values with spaces (never tabs) so that they have the correct field width. The team name is left-justified, and all other fields are right-justified. The ranking always has two digits, including a leading zero if necessary. Spaces will never appear at the beginning or end of lines.

Sample 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

Sample 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

Source

Mid-Central USA 2002

c++代码：

   
  2 #include<stdio.h>
  3 #include<string.h>
  4 
  5 #include<math.h>
  6 
  7 #include<stdlib.h>
  8 
  9 struct rank
 10 
 11 {
 12 
 13 char name[12];
 14 
 15 int sol, tot, g, p[7], ind;//sol 解决题数 tot总时间
 16 
 17 };
 18 
 19 rank r[25];
 20 
 21 int comp(const void *c, const void *d)
 22 
 23 {
 24 
 25 rank *a = (rank *)c; rank *b = (rank *)d;
 26 if(a.sol>b.sol)return 1;
 27 else if(a.sol<b.sol)return -1;
 28 else
 29 {
 30 
 31 if(a.tot<b.tot)return -1;
 32 
 33 else if(a.tot>b.tot) return 1;
 34 
 35 else
 36 
 37 {
 38 
 39 if(a.g>b.g) return 1;
 40 
 41 else if(a.g<b.g)return -1;
 42 
 43 else
 44 
 45 {
 46 
 47 return strcmp(a.name,b.name);
 48 
 49 }
 50 
 51 }
 52 
 53 }
 54 
 55 }
 56 
 57 int main()
 58 
 59 {
 60 int n,cnt=1;
 61 
 62 scanf("%d"，&n);
 63 
 64 if(!n) break;
 65 
 66 for(int i=0;i<n;i++)
 67 
 68 {
 69 
 70 r[i].sol=0;r[i].tot=0;r[i].g=0;
 71 
 72 double t=0;
 73 
 74 scanf("%s",r[i].name);
 75 
 76 for(int i=0;i<7;i++)
 77 
 78 {
 79 
 80 scanf("%d",&r[i].p[j]);
 81 
 82 if(r[i].p[j]>0)
 83 
 84 {
 85 
 86 r[i].sol++;r[i].tot+=r[i].p[j];
 87 
 88 t += log((double)ranks[i].p[j]);
 89 
 90 }
 91 
 92 }
 93 
 94 if(r[i].sol)
 95 
 96 {
 97 
 98 r[i].g=(int)(exp(t/ranks[i].sol) + 0.5);
 99 
100 }
101 
102 }
103 
104 qsort(r,n,sizeof(rank),comp);
105 
106 printf("CONTEST %d
", cnt);
107 
108 cnt++;
109 
110 for(int s= 0; s < n; s++)
111 
112 {
113 
114 if(s < 9)
115 
116 {
117 
118 printf("0");
119 
120 }
121 
122 if(s > 0 && ranks[s].sol == ranks[s-1].sol && ranks[s].tot == ranks[s-1].tot && ranks[s].g == ranks[s-1].g)
123 
124 {
125 
126 ranks[s].ind = ranks[s-1].ind;
127 
128 }
129 
130 else
131 
132 {
133 
134 ranks[s].ind = s + 1;
135 
136 }
137 
138 printf("%d %-10s %d %4d %3d %3d %3d %3d %3d %3d %3d %3d
", ranks[s].ind, ranks[s].name, ranks[s].sol, ranks[s].tot, ranks[s].g,
139 
140 ranks[s].p[0], ranks[s].p[1], ranks[s].p[2], ranks[s].p[3], ranks[s].p[4], ranks[s].p[5], ranks[s].p[6]);
141 
142 }
143 
144 }
145 
146 return 0;
147 
148 }
149 
150

总结：

1.本题参赛队员的数据过多，建议采用结构体数据类型；

2.采用qsort函数进行快速排序，其中的comp函数应当仔细研究；

3.输出格式应该十分小心，一失足成千古恨啊~。