10512  A Day in Mathland
Moderator: Board moderators

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Not so bad this time
Yes my judge solution thinks about this case and handles it but while setting the problem I willfully did not keep two traps to keep it solvable during contest:
a) This trap. Giving such inputs such that x<y
b) Giving such input where the value of x and y will be very nearly integers to give floating point users some trouble.
And now I stick to my generousity although I am a mercyless problemsetter in general
a) This trap. Giving such inputs such that x<y
b) Giving such input where the value of x and y will be very nearly integers to give floating point users some trouble.
And now I stick to my generousity although I am a mercyless problemsetter in general

 Learning poster
 Posts: 54
 Joined: Sun May 18, 2003 1:19 am
 Location: Rio de Janeiro, Brazil
 Contact:
but how does your solution handles it Shahriar ? I've madethe test you suggested, i've created a 84 MB file of X's and Y's, then from this file I generated a P's a Q's file (84 MB of data). Then I ran my program on the P and Q file, and used DIFF on my solution and the original xy file. The result was flawless.
I tried it several times and always flawless results. So, I'm affraid I don't know what else I can do.
This input you are talking about, the 45 4 , my program replies Impossible. Which is correct by the problem statement. What else could I do shaahriar ?
I tried it several times and always flawless results. So, I'm affraid I don't know what else I can do.
This input you are talking about, the 45 4 , my program replies Impossible. Which is correct by the problem statement. What else could I do shaahriar ?
[]s
Mauricio Oliveira Carneiro
Mauricio Oliveira Carneiro

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
mail me
carneiro, mail me your code at shahriar@neksus.com if it is written in C/C++. As I got another Pascal code to judge but could not do it as I don't have a good pascal compiler
One suggestion
I considered one additional thing,
It may be the case that X is an integer, but Y is a floating point value, this case will not yield a desired answer.
It may be the case that X is an integer, but Y is a floating point value, this case will not yield a desired answer.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
You r right
U r right but there is no such inputs in judge input file as I explained. so that does not count. Actually the generator was written in that way.
It does not matter what your code gives output for 45 4, as there is no such input.
It does not matter what your code gives output for 45 4, as there is no such input.
WA Pelase Help
[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]
#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]

 New poster
 Posts: 44
 Joined: Tue Apr 15, 2003 4:31 pm
 Location: Chittagong,Bangladesh
 Contact:
You don't need critical judge data cause you can create it.
by using random function in following equation:
(x+y)*y=p;
(labs(xy))*x=q;
You can create two file in where one is for
x y
and another is for
p q
Now make second file is your problem's(10512) input and first file is judge output.Find difference between your code's output and judge output and solve them.Mind it, input may be negative.
by using random function in following equation:
(x+y)*y=p;
(labs(xy))*x=q;
You can create two file in where one is for
x y
and another is for
p q
Now make second file is your problem's(10512) input and first file is judge output.Find difference between your code's output and judge output and solve them.Mind it, input may be negative.

 Learning poster
 Posts: 83
 Joined: Wed Feb 27, 2002 2:00 am
 Location: Taiwan
I got the same coefficients as carneiro's.carneiro wrote: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 ?
But I have a problem, how can I determine whether b*b4ac is a square number or not?
b*b4ac = (3PQ)^2  4*2*P^2 = P*P+6*P*Q+Q*Q
In worst case, P=Q=(2^311)
and P*P+6PQ+Q*Q will probably larger than 2^64 (unsigned long long)
I wander why long long or double can solve that.
Or I have to get another coeffieients?
I use long long and get acceptI got the same coefficients as carneiro's.
But I have a problem, how can I determine whether b*b4ac is a square number or not?
b*b4ac = (3PQ)^2  4*2*P^2 = P*P+6*P*Q+Q*Q
In worst case, P=Q=(2^311)
and P*P+6PQ+Q*Q will probably larger than 2^64 (unsigned long long)
I wander why long long or double can solve that.
Or I have to get another coeffieients?
I assume the condition which is larger than 2^64 doesn't exist.

 New poster
 Posts: 16
 Joined: Mon Jan 06, 2003 9:27 pm
 Location: Grosskrut, Austria
10512  Where's the tricky input?
Dear Shahriar, dear carneiro,
First of all I want to congratulate You, Shahriar, on this very interesting problem 10512 (A Day in Mathland) which is exactly my taste. I've got AC (after a few "learning cycles") and I've also chosen the "pure" integer arithmetic solution (using long long and a self written sqrtroutine).
I would like to add some remarks to your posting.
I'm quite sure the programmer trying to solve 10512 is able to derive the algebraic equation for X = f(P,Q) and Y = f(Q,X). The "widest" expression within this equation is (P*P + 6P*Q + Q*Q). With the restriction of P < 2^31 and Q < 2^31 this still would need 67(!) bit (signed) integer arithmetic ... which is beyond the Ctype long long. Due to the special "counteracting manner" of the terms (X+Y) in P and (XY) in Q (and the limitation of X and Y to 16 bit signed integer) the valid solutions do in fact leave the upper expression within the range of long long. This does not mean that long long overflows need not be looked after! But they can easily be detected and then are treated as "Impossible.".
The following valid input combination is such a case (result: Impossible.):
1344981044 1749643350
the mathematical solution would actually be: X=52325, Y=18887 (where X is outside the specified 16 bit signed integer range).
I assume that this range of input numbers is also part of the test cases.
I've not really managed to "prove" that PQcombinations with the upper expression beyond 64 bits cannot lead to valid solutions ... but this is what I've learned from my experiments with random test data.
I've learned another thing from the random test data: If you pick an arbitrary XYcombination and calculate P = Y*(X+Y) and Q = X*(XY) as input data from it, the program "always" calculates the same XYcombination as output and never the "2nd possible solution". Even after running through millions of test cases I could not see that happen yet. Due to the restrictions of both solutions having to be integer dividers of P or Q these "two solution cases" are very very rare. Has anybody found one of these yet? They should also be used for the test cases ... but this could also be an idea for another computer programming problem.
Yours, Eric
First of all I want to congratulate You, Shahriar, on this very interesting problem 10512 (A Day in Mathland) which is exactly my taste. I've got AC (after a few "learning cycles") and I've also chosen the "pure" integer arithmetic solution (using long long and a self written sqrtroutine).
I would like to add some remarks to your posting.
I'm quite sure the programmer trying to solve 10512 is able to derive the algebraic equation for X = f(P,Q) and Y = f(Q,X). The "widest" expression within this equation is (P*P + 6P*Q + Q*Q). With the restriction of P < 2^31 and Q < 2^31 this still would need 67(!) bit (signed) integer arithmetic ... which is beyond the Ctype long long. Due to the special "counteracting manner" of the terms (X+Y) in P and (XY) in Q (and the limitation of X and Y to 16 bit signed integer) the valid solutions do in fact leave the upper expression within the range of long long. This does not mean that long long overflows need not be looked after! But they can easily be detected and then are treated as "Impossible.".
The following valid input combination is such a case (result: Impossible.):
1344981044 1749643350
the mathematical solution would actually be: X=52325, Y=18887 (where X is outside the specified 16 bit signed integer range).
I assume that this range of input numbers is also part of the test cases.
I've not really managed to "prove" that PQcombinations with the upper expression beyond 64 bits cannot lead to valid solutions ... but this is what I've learned from my experiments with random test data.
I've learned another thing from the random test data: If you pick an arbitrary XYcombination and calculate P = Y*(X+Y) and Q = X*(XY) as input data from it, the program "always" calculates the same XYcombination as output and never the "2nd possible solution". Even after running through millions of test cases I could not see that happen yet. Due to the restrictions of both solutions having to be integer dividers of P or Q these "two solution cases" are very very rare. Has anybody found one of these yet? They should also be used for the test cases ... but this could also be an idea for another computer programming problem.
Yours, Eric
Can anybody post some tricky Input/Output test cases
Can anybody post some tricky Input/Output test cases.
I have read the previous posts and tried all the cases posted already.
My code passes all those tests but I get WA after 1 second. I still think there must be some tricky test cases where my code fails.
So please post some tricky cases where your AC code passes those tests.
Thanks
I have read the previous posts and tried all the cases posted already.
My code passes all those tests but I get WA after 1 second. I still think there must be some tricky test cases where my code fails.
So please post some tricky cases where your AC code passes those tests.
Thanks

 New poster
 Posts: 2
 Joined: Thu Aug 21, 2003 2:53 pm
 Location: Romania
 Contact:
Printing long long or __int64 fails with cout or printf!?!?!
After I used all the tricks in this section and also used long long and __int64, I got TLE. I tried to print these types with gcc 4.9.8 and Visual C++ with cout or printf and %lld or %I64d and these functions don't know how to print negative numbers!!! Please tell me where's the mistake.
P.S. What is the compiler used by the online Judge? I couldn't find it!
Andrei Csibi.
P.S. What is the compiler used by the online Judge? I couldn't find it!
Andrei Csibi.