F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
Problem 3710. -- [PA2014]Ciagi

3710: [PA2014]Ciagi

Time Limit: 20 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 92  Solved: 10
[Submit][Status][Discuss]

Description

对于两个长度为n的整数数组A=(a[1],a[2],…,a[n]),B=(b[1],b[2],…,b[n]),定义它们的距离为d(A,B)=abs(a[1]-b[1])+abs(a[2]-b[2])+…+abs(a[n]-b[n]),其中abs表示取绝对值。
给定k个整数数组A_1,A_2,…,A_k,定义它们的中心是这样一个整数组成的数组B,使得max{d(A_i,B):i=1,2,…,k}尽可能小

Input

第一行两个整数n,k(2<=n<=100000,2<=k<=5)。n表示数组长度,k表示数组个数。
接下来k行,每行为一个长度为n的数组。数组内整数的绝对值均不超过10^9。

Output

输出一行空格隔开的n个整数,为所求的中心。答案可能有多个,你只需任意输出其中一个。

Sample Input

5 3
1 -1 2 -1 2
1 2 2 1 2
2 2 -1 1 1

Sample Output

1 2 2 1 2

样例解释:
中心到各个数组的距离分别为5,0,5,最大值是5。

HINT

Source

鸣谢Jcvb

[Submit][Status][Discuss]

HOME Back