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

Post by carneiro » Sun Jun 15, 2003 7:06 am

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

Post by lowai » Sun Jun 15, 2003 8:03 am

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:

Post by carneiro » Sun Jun 15, 2003 8:07 am

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

Post by lowai » Sun Jun 15, 2003 8:13 am

i use double.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Hmm

Post by shahriar_manzoor » Sun Jun 15, 2003 2:58 pm

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

Post by lowai » Sun Jun 15, 2003 3:52 pm

can you provide me some test data?

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

10512

Post by Ronaldo » Sun Jun 15, 2003 7:17 pm

I get WA :oops:
#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
New poster
Posts: 5
Joined: Fri May 23, 2003 1:45 pm

Post by Ronaldo » Sun Jun 15, 2003 7:20 pm

:oops:
#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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Thu Jun 19, 2003 1:35 am

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

Post by shahriar_manzoor » Thu Jun 19, 2003 1:54 am

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:

Post by carneiro » Thu Jun 19, 2003 11:38 pm

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

Post by shahriar_manzoor » Fri Jun 20, 2003 12:30 am

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
Location: Chittagong,Bangladesh
Contact:

Post by erfan » Sat Jun 21, 2003 3:42 pm

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
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Sat Jun 21, 2003 6:57 pm

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
Location: Chittagong,Bangladesh
Contact:

Post by erfan » Sun Jun 22, 2003 5:40 am

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

Post Reply

Return to “Volume 105 (10500-10599)”