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

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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
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.

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
hi ronaldo,

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

Dreamer.
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
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
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
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...
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
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? Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
Dreamer#1 wrote: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
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;
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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 10512 A Day in Math-land

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]
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
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
I've read that before I post.
I don't understand what are Baskara coefficients. Can anybody explain to me please?

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
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
Last edited by abishek on Wed Jul 14, 2004 1:16 pm, edited 1 time in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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~ 7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

### 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...)
Just another brick in the wall...

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

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

### 10512 Need Help

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

Thank's In Advance
Rocky