Description

Input

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

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

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

Output

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

Sample Input

3

1 3 4

2 7 3

3 2 1

Sample Output

6

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

题解：

　　看到这题好久了，一直心虚不敢上= =（其实是自己想多了）。

　　一开始以为可以直接算出来，其实也是自己想多了……给了m的范围，n的范围又极其小……然后就是从小到大枚举m，利用扩欧验证是否可行。

 

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 const int N=20; 5 int n, m; 6 int c[N],p[N],l[N]; 7 inline int abs(int x){
   return (x&-1)?-x:x;} 8 inline int gcd(int a,int b){ 9     return b==0?a:gcd(b,a%b);10 }11 inline void exgcd(int a,int b,int &x,int &y){12     if(b==0) {13         x=1;14         y=0;15         return;16     }17     exgcd(b,a%b,x,y);18     int temp=x;19     x=y;20     y=temp-a/b*y;21     return ;22 }23 inline bool check(int mod){24     for(int i=1;i<=n;i++)25         for(int j=i+1;j<=n;j++){26             int a=p[i]-p[j],b=mod,z=c[j]-c[i];27             int t=gcd(a,b);28             if(z%t)  continue;29             int x,y;30             exgcd(a,b,x,y);31             x=x*z/t;32             x%=b/t;33             if(x<0)34                 x+=abs(b/t);35             if(x<=l[i]&&x<=l[j])    return false;36         }37     return true;38 }39 int main(){40     scanf("%d", &n);41     int m=0;42     for(int i=1;i<=n;i++)43         scanf("%d%d%d",c+i,p+i,l+i),m=max(m,c[i]);44     for(m;m<=(int)1e6;m++){45         if(check(m))   break;46     }47     printf("%d\n",m);48 }49 /*50 351 1 3 452 2 7 353 3 2 154 */