10512  A Day in Mathland
Moderator: Board moderators

 Learning poster
 Posts: 54
 Joined: Sun May 18, 2003 1:19 am
 Location: Rio de Janeiro, Brazil
 Contact:
10512  A Day in Mathland
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 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.
[]s
Mauricio Oliveira Carneiro
Mauricio Oliveira Carneiro

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Hmm
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.
10512
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*qarm)%4==0)
{
D2=(p+3*qarm)/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*armq)%arm==0)
{
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*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*armq)%arm==0)
{
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*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;
//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*qarm)%4==0)
{
D2=(p+3*qarm)/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*armq)%arm==0)
{
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*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*armq)%arm==0)
{
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*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*qarm)%4==0)
{
D2=(p+3*qarm)/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*armq)%arm==0)
{
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*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*armq)%arm==0)
{
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*xq)/x;
if((x+y)*y==p && (xy)*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]

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Hmm
By integer solution I mean that no double type variable was used.
Just look at (b(+)sqrt(b*b4*a*c))/(2*a)
if b*b4*a*c is not a square then solution cannot be integer.
If b*b4*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.
Just look at (b(+)sqrt(b*b4*a*c))/(2*a)
if b*b4*a*c is not a square then solution cannot be integer.
If b*b4*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.

 Learning poster
 Posts: 54
 Joined: Sun May 18, 2003 1:19 am
 Location: Rio de Janeiro, Brazil
 Contact:
alright, i've written both solutions, one with doubles and another with integers and my handmade 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 ?
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 ?
[]s
Mauricio Oliveira Carneiro
Mauricio Oliveira Carneiro

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Hmm
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?
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?