Problem1780--2019NH TEA 小学 第六题 中位数(2.7)

1780: 2019NH TEA 小学 第六题 中位数(2.7)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

先科普一下“中位数”的概念。

一个序列被从小到大排序后,排名在中间的那个数就是这个序列的“中位数”。例如,{10,40,30}的中位数是30。

如果序列的长度是偶数,我们会说两个中间元素中较小的一个是中位数。例如,{10,40,30,20}的中位数是20。

有F头奶牛(编号1至F)在参加高考,有M个科目(编号1至M)要考,第i头奶牛的第j个科目的成绩是score[i][j]。

显然,总共有F*M个成绩,我们的目标是使得:这F*M个成绩的中位数是goal。

为了完成这个目标,允许奶牛作弊,现在需要完成如下的任务:

(1)确定一个最小的整数X,其中X表示必须作弊的奶牛的数量。只要修改了某头奶牛的成绩,那么该头奶牛就是作弊。

(2)在确定了最小X的前提下,还要确定一个最小的Y,其中Y表示总共需要修改多少个成绩。

Input

第一行,3个整数:F,M,goal。1 <= F,   1 <= M ,  F * M <= 1000。  0<=goal <= 99。

接下来有F行M列的二维数组,其中第i行第j列的整数是 score[i][j]。0<=score[i][j]<=99。

Output

一行,两个整数, X和Y。

Sample Input Copy

5 5 8
1 2 3 4 5
10 9 8 7 6
25 24 23 22 21
18 16 17 19 20
11 13 12 14 15 

Sample Output Copy

1 5

HINT

样例解释:

如果所有奶牛都不作弊,那么中位数肯定不是8。

X=1,因为只要第3头奶牛作弊就可以达到目标。

第3头奶牛的5个科目成绩都必须修改成不超过8,这样才能使得最终的中位数等于8,所以Y=5。

Source/Category