OJ Board

Hi everyone, yet another Shahriar Manzoor tricky problem

I don't know what else I can do .. I tried the following input full of tricky inputs ... does anybody have any idea?

10
160 48
200 100
300 200
2 0
0 0
1 0
0 1
-1 0
0 -1
0 -4

Can someone please tell me the correct output for that ? mine is :

Case 1:
12 8
Case 2:
Impossible.
Case 3:
20 10
Case 4:
-1 -1
Case 5:
0 0
Case 6:
0 -1
Case 7:
1 0
Case 8:
Impossible.
Case 9:
Impossible.
Case 10:
Impossible.

i also got WA...
my answer is the exactly the same as yours.

There must be some tricky input that we are not seeing. Did you use doubles, or your solution is all made by integers ?

I couldn't find a completely integer solution (i.e. without square roots or divisions)

Maybe there's a integer solution I'm not aware of.

i use double.

The judge solution is based on only integer (long long) however alternate judge solution is written with double by Derek Kisman. So both approach is feasible.

can you provide me some test data?

I get WA
#include<iostream.h>
#include<math.h>
long x,y,p,q;
long A[50000];
int main()
{
bool k;
long E,e,D1,D2,arm;
cin>>E;
bool sxal;
//cout<<(long)sqrt(-9);

for(e=0;e<E;e++)
{
k=1;
sxal=1;
cin>>p>>q;
long h;
/*
if(p==0 && q==0)
{
cout<<"Case "<<e+1<<":\n";
cout<<p<<" "<<p<<endl;
continue;

}
if(p==0 && q==1)
{
cout<<"Case "<<e+1<<":\n";
cout<<q<<" "<<p<<endl;
continue;

}
if(p==1 && q==0)
{
cout<<"Case "<<e+1<<":\n";
cout<<"0 -1"<<endl;
continue;

}
*/

D1=(long)pow(p+3*q,2)-8*q*q;
arm=(long)sqrt(D1);
if(D1<0 || arm*arm!=D1)
{
cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";
continue;
}

if((p+3*q-arm)%4==0)
{
D2=(p+3*q-arm)/4;
if(D2>=0)
{
arm=(long)sqrt(D2);
if(arm==0)
{
if(p>=0)
{
h=(long)sqrt(p);
if(h*h==p)
{
x=arm;
y=-h;
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
}
goto qqq;
}
if(arm*arm==D2 && (arm*arm-q)%arm==0)
{
x=-arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}

}
}
}
qqq:
arm=(long)sqrt(D1);
if((p+3*q+arm)%4==0)
{
D2=(p+3*q+arm)/4;
if(D2>=0)
{
arm=(long)sqrt(D2);
if(arm==0)
{
if(p>=0)
{
h=(long)sqrt(p);
if(h*h==p)
{
x=arm;
y=-h;
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
else
{
cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";
continue;
}
}
else
{
cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";
continue;
}

}
if(arm*arm==D2 && (arm*arm-q)%arm==0)
{
x=-arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
}
}
}


cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";


}

return 0;

}[cpp][/cpp]

#include<iostream.h>
#include<math.h>
long x,y,p,q;
long A[50000];
int main()
{
bool k;
long E,e,D1,D2,arm;
cin>>E;
bool sxal;

for(e=0;e<E;e++)
{
k=1;
sxal=1;
cin>>p>>q;
long h;

D1=(long)pow(p+3*q,2)-8*q*q;
arm=(long)sqrt(D1);
if(D1<0 || arm*arm!=D1)
{
cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";
continue;
}

if((p+3*q-arm)%4==0)
{
D2=(p+3*q-arm)/4;
if(D2>=0)
{
arm=(long)sqrt(D2);
if(arm==0)
{
if(p>=0)
{
h=(long)sqrt(p);
if(h*h==p)
{
x=arm;
y=-h;
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
}
goto qqq;
}
if(arm*arm==D2 && (arm*arm-q)%arm==0)
{
x=-arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}

}
}
}
qqq:
arm=(long)sqrt(D1);
if((p+3*q+arm)%4==0)
{
D2=(p+3*q+arm)/4;
if(D2>=0)
{
arm=(long)sqrt(D2);
if(arm==0)
{
if(p>=0)
{
h=(long)sqrt(p);
if(h*h==p)
{
x=arm;
y=-h;
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
else
{
cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";
continue;
}
}
else
{
cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";
continue;
}

}
if(arm*arm==D2 && (arm*arm-q)%arm==0)
{
x=-arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
}
}
}


cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";


}

return 0;

}[cpp][/cpp]

Shahriar, when you say only integer solution you mean that truncations were made or that there is no division or square roots ?

I used all my mathematics trying to find a completely integer solution for the problem, but just couldn't find it.

By integer solution I mean that no double type variable was used.

Just look at (-b(+-)sqrt(b*b-4*a*c))/(2*a)

if b*b-4*a*c is not a square then solution cannot be integer.

If b*b-4*a*c is an square number but the numerator is not divisible by 2*a then the answer is not an integer.

So I used only a handwritten sqrt function(using binary search) and % operator. The approach using double is simpler and faster (to code) but can have many errors if one is not careful.

alright, i've written both solutions, one with doubles and another with integers and my hand-made sqrt with binary search, using long long, and both still WA.

My Baskara coeficients are :

a = 2;
b = ((-3)*P) - Q;
c = P*P;

this is for finding (y*y). Isn't that wrigth Shahriar ?

My input case is :

13
160 48
200 100
300 200
2 0
0 0
1 0
0 1
-1 0
0 -1
0 -4
0 4
0 256
0 343

and the output for that is :

Case 1:
12 8
Case 2:
Impossible.
Case 3:
20 10
Case 4:
-1 -1
Case 5:
0 0
Case 6:
0 -1
Case 7:
1 0
Case 8:
Impossible.
Case 9:
Impossible.
Case 10:
Impossible.
Case 11:
2 0
Case 12:
16 0
Case 13:
Impossible.


Where can I still be wrong .. i mean, in both codes. There seems to be something I didn't get yet.

The special case when P == 0 and no solution is found by the baskara formula, I make y=0 , then X*X = Q, and get the only positive integer root from Q (if there is one). Is that correct? Or should I treat this case more carefuly ?

Since you are spending so much time on this problem what you can do is simply create a file large with random values for x and y. The file will be like

10 20
30 40
346 347 etc

Now from this values of x and y produce another file of p and q. Then try with your program if the original answers come. Also create another file with random values of p and q and as far as I know all of them should report impossible. Give input of some values of p and q which was generated by equal values of x and y. Have u considered the cases where there is really more than one solution and you will have to output the one with less x value?

I got AC but i have a question.If the input is 420 19 then what's the output?
Again for 45 4 what's the output.

I am very confused for it though i got AC.

for input 45 4, X = 4 and Y = 5 is not a valid solution since X >= Y according to the very first line of the problem statement. so the output should be "Impossible." hope this clears the confusion.

Yah i was not confuse but in my one of AC code result is: 4 5
I think how it AC?