记录编号	175118	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]荒岛野人	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	1.499 s
提交时间	2015-08-04 17:09:39	内存使用	0.29 MiB

#include<cstdio>
#define ABS(A) ((A)>0?(A):(-(A)))
using namespace std;
int n,m,x,y,C,ee,c[22],p[22],age[22];
bool no;
inline int gc_d(int a,int b)
{
    while(b)
    {
        ee=a%b;
        a=b;
        b=ee;
    }
    return a;
}
inline int sov(int a,int b)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	int ans=sov(b,a%b);
	int temp=x;
	x=y;
	y=temp-a/b*y;
	return ans;
}
int main()
{
    freopen("savage.in","r",stdin);
    freopen("savage.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&c[i],&p[i],&age[i]);
        if(m<c[i])
            m=c[i];
    }
    int a,b,gcd;
    for(int i=m;;++i)
    {
        no=0;
        for(int j=1;j<=n;++j)
        {    
            for(int k=j+1;k<=n;++k)
            {
				b=i;
                a=p[j]-p[k];
                C=c[k]-c[j];
                gcd=gc_d(a,b);
                if(C%gcd)
                    continue;
                a/=gcd;
            	b/=gcd;
                sov(a,b);
                x=x*C/gcd;
                x%=ABS(b);
                if(x<0)
                    x+=ABS(b);
                if(x<=age[k]&&x<=age[j])
                {
                    no=1;
                    break;
                }
            }
            if(no)
                break;
        }
        if(!no)
        {
            printf("%d",i);
            //while(1);
            return 0;
        }
    }
}