记录编号	455718	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]荒岛野人	最终得分	100
用户昵称	hee	是否通过	通过
代码语言	C++	运行时间	0.592 s
提交时间	2017-10-02 20:27:11	内存使用	0.31 MiB

#include<bits/stdc++.h>
#define ll long long
#define RG register
#define il inline
#define N
using namespace std;int _max;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void exgcd(int a,int b,int & x,int & y){
  if(!b){x=1,y=0;return;}
  exgcd(b,a%b,y,x),y-=x*(a/b);
}
struct Dat{
  int C,P,L;
  void read(){scanf("%d%d%d",&C,&P,&L);_max=max(C,_max);}
}a[20];
int n;
int main(){
  freopen("savage.in","r",stdin);
  freopen("savage.out","w",stdout);
  scanf("%d",&n);
  for(int i=1;i<=n;++i)a[i].read();
  for(int ans=_max;;ans++){
    bool flag=true;
    for(int i=1;i<=n&&flag;++i){
      for(int j=1;j<i&&flag;++j){
	int c1=a[i].C,c2=a[j].C;
	int p1=a[i].P,p2=a[j].P;
	if(p1==p2)continue;
	int l1=a[i].L,l2=a[j].L;
	if(p2>p1)swap(c1,c2),swap(p1,p2),swap(l1,l2);
	int a=p1-p2,b=ans,Gcd=gcd(a,b),C=c2-c1;
	if((C/Gcd)*Gcd!=C)continue;
	int x,y;exgcd(a/Gcd,b/Gcd,x,y);
	x*=C/Gcd;
	while(x<=0)x+=ans/Gcd;
	while(x-ans/Gcd>0)x-=ans/Gcd;
	if(x<=min(l1,l2)){flag=false;break;}
      }
    }
    if(flag)cout<<ans,exit(0);
  }
  return 0;
}