10512 - A Day in Math-land
Moderator: Board moderators
-
- New poster
- Posts: 2
- Joined: Thu Aug 21, 2003 2:53 pm
- Location: Romania
- Contact:
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.
I hope Shahriar will help me clear this doubt.
Andrei Csibi.
What is correct output for:
?
I've got a solution that gets WA but all test data I tried gives correct results AFAIK ...
Ciao!!!
Claudio
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
I can't remember exactly what was asked in this problem.
My AC Solution gives:
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...
My AC Solution gives:
Code: Select all
Case 1:
-32767 -32767
hope it helps...
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.
Some more input/outputs :
Are you still getting WA?
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.
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.
My program was correct about you inputs...Dreamer#1 wrote:Are you still getting WA?
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
Code: Select all
Case 1:
1 -1
Case 2:
1 -1
Many thanks for the answer!
Ciao!!!
Claudio
-
- Learning poster
- Posts: 95
- Joined: Mon Apr 26, 2004 1:23 pm
- Location: Hong Kong and United States
- Contact:
10512 A Day in Math-land
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]
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]
Re: 10512 A Day in Math-land
This loop is slow to go through for every input...cytmike wrote: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]
Look at this thread for some hints on how to find directly a solution...
Ciao!!!
Claudio
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
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
Last edited by abishek on Wed Jul 14, 2004 1:16 pm, edited 1 time in total.
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~
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~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
small mistake
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...)
Abi you might want to recheck that formula.You are missing something in the denominator...
(I heard you program very well...)
Just another brick in the wall...
-
- New poster
- Posts: 1
- Joined: Mon Jul 12, 2004 2:32 pm
10512 WA Help~~~
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]
[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
Can Any Body Give Some Special Data For This Problem.
It Help Me Very Much.
Thank's In Advance
Rocky
It Help Me Very Much.
Thank's In Advance
Rocky