首页 > ACM题库 > HDU-杭电 > HDU 4596-Yet another end of the world-数论-[解题报告]HOJ
2015
09-17

HDU 4596-Yet another end of the world-数论-[解题报告]HOJ

Yet another end of the world

问题描述 :

In the year 3013, it has been 1000 years since the previous predicted rapture. However, the Maya will not play a joke any more and the Rapture finally comes in. Fortunately people have already found out habitable planets, and made enough airships to convey all the human beings in the world. A large amount of airships are flying away the earth. People all bear to watch as this planet on which they have lived for millions of years. Nonetheless, scientists are worrying about anther problem…
As we know that long distance space travels are realized through the wormholes, which are given birth by the distortion of the energy fields in space. Airships will be driven into the wormholes to reach the other side of the universe by the suction devices placed in advance. Each wormhole has its configured attract parameters, X, Y or Z. When the value of ID%X is in [Y,Z], this spaceship will be sucked into the wormhole by the huge attraction. However, the spaceship would be tear into piece if its ID meets the attract parameters of two wormholes or more at the same time.
All the parameters are carefully adjusted initially, but some conservative, who treat the Rapture as a grain of truth and who are reluctant to abandon the treasure, combine with some evil scientists and disrupt the parameters. As a consequence, before the spaceships fly into gravity range, we should know whether the great tragedy would happen or not. Now the mission is on you.

输入:

Multiple test cases, ends with EOF.
In each case, the first line contains an integer N(N<=1000), which means the number of the wormholes.
Then comes N lines, each line contains three integers X,Y,Z(0<=Y<=Z<X<2*109).

输出:

Multiple test cases, ends with EOF.
In each case, the first line contains an integer N(N<=1000), which means the number of the wormholes.
Then comes N lines, each line contains three integers X,Y,Z(0<=Y<=Z<X<2*109).

样例输入:

2
7 2 3
7 5 6
2
7 2 2
9 2 2

样例输出:

Can Take off
Cannot Take off

这题分两种情况:

1.如果存在两个区间重叠,一定满足条件。

2.如果不存在两个区间重叠,那么id%x1=a,id%x2=b,a,b分别在[y1,z1],和[y2,z2]这两个区间内。

id=x1*s+a=x2*t+b;

x1*s+x2*t=a-b;

所以只要判断这个方程有解即可。

gcd(x1,x2)=x1*s+x2*t;

只要(a-b)%gcd(x1,x2)==0即可,求出(a-b)的范围,问题就等价于gcd(x1,x2)或者gcd(x1,x2)的倍数在范围内即可。

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 1005
using namespace std;
int n;
inline int rd(int &x)
{
    char c=getchar();
    while(!isdigit(c))c=getchar();
    x=0;
    while(isdigit(c))
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
struct node
{
    int x,y,z;
} a[maxn];
bool cmp(node x1,node x2)
{
    if(x1.y==x2.y) return x1.z<x2.z;
    else
        return x1.y<x2.y;
}
int gcd(int a,int b)
{
    if(!b) return a;
    else return gcd(b,a%b);
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<n; i++)
        {
            rd(a[i].x);rd(a[i].y);rd(a[i].z);
//            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
        }
        if(n<=1)
        {
            printf("Can Take off\n");
            continue;
        }
        sort(a,a+n,cmp);
//        for(int i=0;i<n;i++)
//        {
//            cout<<a[i].x<<' '<<a[i].y<<' '<<a[i].z<<endl;
//        }
        int flag=0;
        for(int i=0; i<n-1; i++)
        {
            int l1=a[i].y,r1=a[i].z,l2=a[i+1].y,r2=a[i+1].z;
            int x1=a[i].x,x2=a[i+1].x;
            if(l2<=r1)
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
        {
            printf("Cannot Take off\n");
            continue;
        }
        for(int i=0;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                 int l1=a[i].y,r1=a[i].z,l2=a[j].y,r2=a[j].z;
                 int x1=a[i].x,x2=a[j].x;
                 int Max=r2-l1,Min=l2-r1;
                 int d=gcd(x1,x2);
                 if((Min<=d&&d<=Max)||d<=(Max-Min+1))
                 {
                     flag=1;
                     break;
                 }
            }
            if(flag==1)
            {
                break;
            }
        }
        if(flag==1)
        {
            printf("Cannot Take off\n");
        }
        else
        {
            printf("Can Take off\n");
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/qq415200973/article/details/10035131