#P5778. [CTSC2001] GPA 排名系统

[CTSC2001] GPA 排名系统

题目描述

目前,高等院校往往采用 GPA (Grade Point Average) 来评价学生的学术表现。传统的排名方式是求每一个学生的平均成绩,以平均成绩作为依据进行排名。

但是这样的排名方法已经引起了教育界以及社会各界人士的争议。因为它存在着许多弊端。对于不同的课程,选课学生的平均成绩会不同程度地受到课程的难易程度和老师的严厉程度的制约。因而这样的排名系统无形中就鼓励了学生选择一些比较容易的课程,因为这样可以事半功倍地获得较高的平均分。

为了克服这些弊端,我们需要对排名系统做一定的改进。

一种改进的方案是对选第 ii 门课的每一个学生的成绩加上一个特定的修正值 did_i,例如编号为 jj 的学生该课的成绩 GijG_{ij} 修改为 Gij=Gij+diG’_{ij}=G_{ij}+d_i。最终使得经过调整后,该课的平均分等于选该课的所有学生的所有课的平均分。对每一门课都做这样的调整,使得上述条件对所有课程都满足。这种调整方案一定程度地避免了传统排名系统的不公正。而你的任务正是根据一个大学某一个年级学生某学年的成绩,给出他们的排名。假设每一个学生都至少选一门课。

输入格式

第一行是两个正整数 mmnn,分别表示学生人数和课程数目。

接下来 mm 行是一个矩阵,矩阵中第 ii 行的第 jj 个元素表示第 ii 个学生第 jj 门课的成绩 GijG_{ij}。如果该学生没有选这门课,那么 Gij1G_{ij}=-1。由于该方案的施行只是为了获得更加科学的排名,因此调整后的成绩的数值大小本身没有什么意义,因此调整后的成绩可以不是 01000\sim 100 之间的数。

输出格式

输出采用改进方案后这些学生的排名。以学生编号的形式输出,每行是一个学生的编号。

如果在上述调整后,有若干学生平均分相等(精确到小数点后的三位),则他们的名次相同,按照字典序输出。

当然许多时候,上述调整无法顺利进行,即调整的目标无法达到。(因此,在实际问题中,我们往往在最小二乘意义下获得一种最接近目标的调整方案。)也有可能或者因调整不唯一而不能确定学生的名次。若以上两种情况发生,则输出 fail

4 2
60 -1
70 -1
80 45
-1 65
4
3
2
1

提示

样例解释

一种可行的调整方法是:

第一门课每一个学生的成绩加上 1010,第二门课每一个学生的成绩加上 3535。 调整后的情况是:

70 –1
80 –1
90 80
-1 100

调整后第一门课的平均分为:(7080+90)/3=80(70+80+90)/3=80,选第一门课的所有学生的所有课的平均分为:(70+80+90+80)/4=80(70+80+90+80)/4=80

第二门课的平均分为:(80+100)/2=90(80+100)/2=90,选第二门课的所有学生的所有课的平均分为:(90+80+100)/3=90(90+80+100)/3=90

然后,计算每一个学生的平均分并且排名,即得到了输出的结果。

数据范围

对于全部数据,1m5001\le m\le 5001n1001\le n\le 1001Gij100-1\le G_{ij}\le 100