description:
solution:
观察到答案并不会很大,于是我们可以枚举答案(这里不满足单调性,不能二分)
对于任意的i,j,原式可变形 为 (Pi−Pj)∗x−M∗y=Cj−Ci
于是这就是一个exgcd的模型
最后求出如果x不存在或者超过了野人的寿命m就是答案,否则就继续找。
code:
#include<cstdio>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int n;
int c[17],p[17],l[17];
int check(int m)
{
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int A=p[i]-p[j];
int B=m;
int C=c[j]-c[i];
int x,y;
int ans=exgcd(A,B,x,y);
if(C%ans)continue;
A/=ans;
B/=ans;
C/=ans;
if(B<0)B=-B;
x=(x*C%B+B)%B;
if(x<=l[i]&&x<=l[j])return 0;
}
}
return 1;
}
int max(int x,int y)
{
if(x>=y)return x;
return y;
}
int main()
{
scanf("%d",&n);
int start=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&c[i],&p[i],&l[i]);
start=max(start,c[i]);
}
for(int i=start;i;i++)
{
if(check(i))
{
printf("%d\n",i);
return 0;
}
}
}