Code: Select all
#include <cstdio>
#include <iostream>
#include <cmath>
#include <memory>
#define MAX 100
using namespace std;
bool mark[MAX];
bool graph[MAX][MAX];
long long elevator[MAX][2],queue[MAX];
long long GCD(long long a,long long b)
{
if(b==0)
{
return a;
}
else
{
return GCD(b,a%b);
}
}
void calculate(long long x1,long long x2,long long *i,long long *j)
{
long long y1,y2,z1,z2,gcd;
gcd=GCD(x1,x2);
y1=x1/gcd;
y2=x2/gcd;
if((*i<0)||(*j<0))
{
z1=1-(*i+1)/y2;
z2=1-(*j+1)/y1;
if(z1<z2)
{
*i=*i+z2*y2;
*j=*j+z2*y1;
}
else
{
*i=*i+z1*y2;
*j=*j+z1*y1;
}
}
if((*i>=y2)&&(*j>=y1))
{
z1=*i/y2;
z2=*j/y1;
if(z1<z2)
{
*i=*i-z1*y2;
*j=*j-z1*y1;
}
else
{
*i=*i-z2*y2;
*j=*j-z2*y1;
}
}
}
bool diophantine(long long z,long long x1,long long x2,long long *i,long long *j)
{
if(z==0)
{
*i=0;
*j=0;
return true;
}
else if(x1==0)
{
if(z%x2!=0)
{
return false;
}
else
{
*i=0;
*j=(-z)/x2;
return true;
}
}
else if(x2==0)
{
if(z%x1!=0)
{
return false;
}
else
{
*i=z/x1;
*j=0;
return true;
}
}
else
{
if(x1<=x2)
{
if(diophantine(z,x1,x2%x1,i,j)==false)
{
return false;
}
else
{
*i=*i+(*j)*(x2/x1);
calculate(x1,x2,i,j);
return true;
}
}
else
{
if(diophantine(-z,x2,x1%x2,j,i)==false)
{
return false;
}
else
{
*j=*j+(*i)*(x1/x2);
calculate(x1,x2,i,j);
return true;
}
}
}
}
bool test(long long f,long long f1,long long x1,long long f2,long long x2)
{
long long i,j;
if(diophantine(f2-f1,x1,x2,&i,&j)==false)
{
return false;
}
if((i>=0)&&(i<f)&&(j>=0)&&(j<f))
{
return true;
}
else
{
return false;
}
}
bool divide(long long p,long long q)
{
if(q==0)
{
if(p==0)
{
return true;
}
else
{
return false;
}
}
else
{
if(p%q==0)
{
return true;
}
else
{
return false;
}
}
}
int main()
{
//freopen("718.in","r",stdin);
//freopen("718.out","w",stdout);
long long a,b,e,f,i,j,n,p,q,s,size;
cin >> n;
for(i=0;i<n;i++)
{
memset(mark,0,sizeof(mark));
cin >> f >> e >> a >> b;
for(j=0;j<e;j++)
{
cin >> elevator[j][1] >> elevator[j][0];
}
for(p=0;p<e;p++)
{
for(q=0;q<e;q++)
{
if(test(f,elevator[p][0],elevator[p][1],elevator[q][0],elevator[q][1])==true)
{
graph[p][q]=true;
}
else
{
graph[p][q]=false;
}
}
}
size=0;
for(j=0;j<e;j++)
{
if((a>=elevator[j][0])&&(divide(a-elevator[j][0],elevator[j][1])==true))
{
mark[j]=true;
queue[size++]=j;
}
}
while(size!=0)
{
s=queue[--size];
for(j=0;j<e;j++)
{
if((graph[s][j]==true)&&(mark[j]==false))
{
mark[j]=true;
queue[size++]=j;
}
}
}
for(j=0;j<e;j++)
{
if((mark[j]==true)&&(b>=elevator[j][0])&&(divide(b-elevator[j][0],elevator[j][1])==true))
{
cout << "It is possible to move the furniture." << endl;
break;
}
}
if(j>=e)
{
cout << "The furniture cannot be moved." << endl;
}
}
return 0;
}
.
but I'm pretty sure that the sentence means 