10512 - A Day in Math-land

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

10512 - A Day in Math-land

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.
[]s
Mauricio Oliveira Carneiro

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm
i also got WA...
my answer is the exactly the same as yours.

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

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm
i use double.

shahriar_manzoor
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.

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm
can you provide me some test data?

Ronaldo
New poster
Posts: 5
Joined: Fri May 23, 2003 1:45 pm

10512

I get WA #include<iostream.h>
#include<math.h>
long x,y,p,q;
long A;
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
New poster
Posts: 5
Joined: Fri May 23, 2003 1:45 pm #include<iostream.h>
#include<math.h>
long x,y,p,q;
long A;
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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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.
[]s
Mauricio Oliveira Carneiro

shahriar_manzoor
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*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
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 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 ?
[]s
Mauricio Oliveira Carneiro

shahriar_manzoor
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?

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:
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.

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
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
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm