10512 - A Day in Math-land

[shamim]

The judge compiler is similar to the GNU C++ standard.
For windows, the compiler provided with cygwin is most similar than any other i know.

Why do you need to consider long long. Simply use double; i got AC using double.

[AndreiCsibi]

I used double, the standard sqrt and I also tried one written by me(with binary search) and the result is the same: Time Limit Exceeded! I understood that the official solution is based on a sqrt function written with binary search. I believe that something has changed in the evaluator. I wonder if the old solutions that got AC could get the same result now.
I hope Shahriar will help me clear this doubt.

Andrei Csibi.

[Dreamer#1]

hi ronaldo,

hope you got my message. your problem must be solved by now.

regards,

Dreamer.

[CDiMa]

What is correct output for:

Code: Select all

1
2147352578 0

?
I've got a solution that gets WA but all test data I tried gives correct results AFAIK ...

Ciao!!!

Claudio

[Dreamer#1]

I can't remember exactly what was asked in this problem.

My AC Solution gives:

Code: Select all

Case 1:
-32767 -32767

If you think its not correct then there must be no such input at the Judge but most probably its the correct output.

hope it helps...

[Dreamer#1]

Some more input/outputs :

Code: Select all

6 
2147352578 0
0 0 
1 0 
0 -1 
1 1 
-1 -3

Case 1:
-32767 -32767
Case 2:
0 0
Case 3:
0 -1
Case 4:
Impossible.
Case 5:
Impossible.
Case 6:
Impossible.

Are you still getting WA?

[CDiMa]

Are you still getting WA?

My program was correct about you inputs...
and finally I found the problem. In one case I divided by two without checking that the dividend was even so that the sample input

Code: Select all

2
0 2
0 3

gave the incorrect answer:

Code: Select all

Case 1:
1 -1
Case 2:
1 -1

Obviously fixing the bug I broke the logic of my prog and had to struggle a little bit more to get finally accepted.

Many thanks for the answer!

Ciao!!!

Claudio

[cytmike]

I got TLE no matter i preprocess or calculates it every time.
Can anybody teach me the correct algo?


[cpp]
#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

int main()
{
int p;
cin>>p;

int sq[32770];
for (int h=1;h<=32768;h++)
sq[h]=h*h;

for (int h=1;h<=p;h++)
{
cout<<"Case "<<h<<":\n";
double i,s;
cin>>i>>s;

int hp=0,sky=0;

for (int h=floor(sqrt((i+s)/2));h<=32768&&sq[h]<=i+s;h++)
{

double y=i+s-sq[h];
int l=sqrt(y);//cout<<h<<' '<<y<<' '<<l<<endl;
if (abs(l*l-y)<1e-4)
{
sky=l;
hp=h;
break;
}
}

if (!hp)
cout<<"Impossible.\n";
else
cout<<hp<<' '<<sky<<endl;
}
return 0;
} [/cpp]

[CDiMa]

I got TLE no matter i preprocess or calculates it every time.
Can anybody teach me the correct algo?


[cpp]
for (int h=1;h<=p;h++)
{
cout<<"Case "<<h<<":\n";
double i,s;
cin>>i>>s;

int hp=0,sky=0;

for (int h=floor(sqrt((i+s)/2));h<=32768&&sq[h]<=i+s;h++)
{
[/cpp]

This loop is slow to go through for every input...
Look at this thread for some hints on how to find directly a solution...

Ciao!!!

Claudio

[cytmike]

I've read that before I post.
I don't understand what are Baskara coefficients. Can anybody explain to me please?

[abishek]

they are nothing but the coefficients a, b, c of the quadratic,

ax^2+bx+c=0

the general solution to this i think is first referred by Bhaskara.
that is all

x= (-b+sqrt(det))/2a and (-b-sqrt(det))/2a are the solutions, with (edited after helmets post)

det = b*b- 4*a*c

hope it helps
bye
abi

[Observer]

Yeah, this is just a quadratic equation solving task. Read previous topics.

By the way, I think the test data for this problem is very well-designed. It covers all kinds of cases, not accepting any wrong solutions, yet does not cause much precision/overflow etc. errors, making it actually solvable... Nice~

[helmet]

Just a thanks to everyone for everything...sample IO.

Abi you might want to recheck that formula.You are missing something in the denominator...

(I heard you program very well...)

[FinalLaugh]

I don't know why......need biginteger

[cpp]#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cassert>

using namespace std;

#ifdef ONLINE_JUDGE
istream& in = cin;
#else
ifstream in("test.in");
#endif

void calc(double ySq,double &x,double &y,double p,double q,bool &ansed){
double tmpx,tmpy;
if (fabs(ySq)<0.0000001){
tmpx=sqrt(q);
if (fmod(tmpx,1)==0){
x=tmpx;
y=0.0;
ansed=true;
}
return;
}
if (ySq>=0){
tmpy=sqrt(ySq);
tmpx=(p-ySq)/tmpy;
if (tmpx<x&&fmod(tmpx,1)==0&&fmod(tmpy,1)==0){
x=tmpx;
y=tmpy;
ansed=true;
}

tmpy=-sqrt(ySq);
tmpx=(p-ySq)/tmpy;
if (tmpx<x&&fmod(tmpx,1)==0&&fmod(tmpy,1)==0){
x=tmpx;
y=tmpy;
ansed=true;
}
}
}

int main(){
int n;
in>>n;
int caseNum=1;
while (n--){
cout<<"Case "<<caseNum<<":"<<endl;
caseNum++;
bool ansed=false;
double x=2e64,y=2e64;
double p,q;
in>>p>>q;
double a=0.0,b=0.0,c=0.0;
double ySq1=0.0,ySq2=0.0,xSq=0.0,delta=0.0;
a=2;
b=-(3*p+q);
c=p*p;
delta=b*b-4*a*c;
if (delta>=0){
ySq1=(-b+sqrt(delta))/(2.0*a);
ySq2=(-b-sqrt(delta))/(2.0*a);
calc(ySq1,x,y,p,q,ansed);
calc(ySq2,x,y,p,q,ansed);
}

if (!ansed){
cout<<"Impossible."<<endl;
}
else cout<<x<<" "<<y<<endl;
}

#ifndef ONLINE_JUDGE
system("pause");
#endif
return 0;
}[/cpp]

[Rocky]

Can Any Body Give Some Special Data For This Problem.
It Help Me Very Much.

Thank's In Advance
Rocky