PID511 / 神迹初窥
题目描述

密码破解了,令人惊叹的是神书上只有一幅地图,指引着它的有缘人来到……

题目描述:

地图上有n个3维空间的点,它们的坐标分别为(xi,yi,zi),现在,每个点都有一个瑕疵度,瑕疵度的定义(有些晦涩,请结合例子仔细阅读):对于第i个点的xi与zi,若每次产生一个当前最小的(a*xi+b*zi)(a、b为任意非负整数),若干次后当产生的数大于等于(a0*xi +b0*zi)时,可以表示以后所有的自然数,则该点瑕疵度wi为(a0*xi +b0*zi),如:xi=2,zi=5,得到2,4(=2*2),5,6(=3*2),7(=1*2+1*5),8(=4*2),9(=2*2+1*5)),10(=2*5或=5*2)……从第2项的4开始以后的自然数都可以得到,瑕疵度为4;若不能得到,则瑕疵度为min(xi,zi)的平方。神迹处在坐标系中,且这n个点到神迹的距离(距离为曼哈顿距离,即每一维坐标差的绝对值之和)与瑕疵度的乘积之和最小。

数据范围 0<n<100000,0<wi<5000

输入格式

第一行,一个数n

接下来n行,每行3个数xi,yi,zi

输出格式

一行,找到点的坐标 (a,b,c)

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论