10512 - A Day in Math-land

[carneiro]

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.

[lowai]

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

[carneiro]

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.

[lowai]

i use double.

[shahriar_manzoor]

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.

[lowai]

can you provide me some test data?

[Ronaldo]

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]

[Ronaldo]

#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]

[carneiro]

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.

[shahriar_manzoor]

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.

[carneiro]

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 ?

[shahriar_manzoor]

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?

[erfan]

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.

[Adil]

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.

[erfan]

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