Page 3 of 4

Posted: Mon Sep 01, 2003 12:39 pm
by 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. :wink:

Posted: Mon Sep 01, 2003 8:57 pm
by 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.

Posted: Wed Jan 14, 2004 4:13 pm
by Dreamer#1
hi ronaldo,

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

regards,

Dreamer.

Posted: Thu Jan 22, 2004 4:50 pm
by 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

Posted: Thu Jan 22, 2004 8:36 pm
by Dreamer#1
I can't remember exactly what was asked in this problem. :oops:

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

Posted: Thu Jan 22, 2004 8:41 pm
by 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? :roll:

Posted: Fri Jan 23, 2004 11:31 am
by CDiMa
Dreamer#1 wrote:Are you still getting WA? :roll:
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 8) and had to struggle a little bit more to get finally accepted.

Many thanks for the answer!

Ciao!!!

Claudio

10512 A Day in Math-land

Posted: Thu Jun 24, 2004 3:05 am
by cytmike
I got TLE no matter i preprocess or calculates it every time.
Can anybody teach me the correct algo?
:cry:

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

Re: 10512 A Day in Math-land

Posted: Fri Jun 25, 2004 5:58 pm
by CDiMa
cytmike wrote:I got TLE no matter i preprocess or calculates it every time.
Can anybody teach me the correct algo?
:cry:

[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

Posted: Sat Jun 26, 2004 2:38 pm
by cytmike
I've read that before I post.
I don't understand what are Baskara coefficients. Can anybody explain to me please?

Posted: Sat Jun 26, 2004 8:00 pm
by 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

Posted: Sun Jun 27, 2004 10:14 am
by 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~ :wink:

small mistake

Posted: Wed Jul 14, 2004 10:07 am
by 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...)

10512 WA Help~~~

Posted: Mon Jul 19, 2004 9:01 am
by 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]

10512 Need Help

Posted: Thu Apr 21, 2005 11:04 am
by Rocky
Can Any Body Give Some Special Data For This Problem.
It Help Me Very Much.

Thank's In Advance
Rocky