Eva

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 3112  Solved: 1422
Description

第1行为一个整数N(1<=N<=15)，即野人的数目。

第2行到第N+1每行为三个整数Ci, Pi, Li表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。

(1<=Ci,Pi<=100, 0<=Li<=10^6 )

仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于10^6。

3
1     3      4
2     7      3
3     2      1

6
//该样例对应于题目描述中的例子。

/**************************************************************

    Problem: 1407

    User: ictsing

    Language: C++

    Result: Accepted

    Time:988 ms

    Memory:1288 kb

****************************************************************/

 

//BZOJ1407 [Noi2002]Savage

#include <iostream>

#include <cstdio>

using namespace std;

const int mt = 20+5;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

       ch=getchar();

       if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

       num=num*10+ch-'0';

       ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int cc[mt],p[mt],l[mt];

int n;

int gcd(int x,int y)

{

    if(y==0) return x;

    return gcd(y,x%y);

}

void exgcd(int a,int b,int &x,int &y)

{

    if(b==0) x=1,y=0;

    else exgcd(b,a%b,y,x),y-=x*(a/b);

}

bool judge(int m)

{

    int a,b,c,t,x,y;

    for(int i=1;i<=n;i++)

        for(int j=i+1;j<=n;j++)

        {

            a=p[i]-p[j],b=m,c=cc[j]-cc[i];

            t=gcd(a,b);

            if(c%t==0)

            {

                a/=t,b/=t,c/=t;

                exgcd(a,b,x,y);

                if(b<0) b=-b;

                x=((x*c)%b+b)%b;

                if(!x) x+=b;

                if(x<=min(l[i],l[j]))

                    return 0;

            }

        }

    return 1;

}

int main()

{

    n=read();

    int mx=0;

    for(int i=1;i<=n;i++)

        cc[i]=read(),p[i]=read(),l[i]=read(),mx=max(mx,cc[i]);

    for(int i=mx;;i++)

        if(judge(i)) 

        {

            printf("%d",i);

            break;

        }

    return 0;

}