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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon Sep 01, 2003 12:39 pm

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:

AndreiCsibi
New poster
Posts: 2
Joined: Thu Aug 21, 2003 2:53 pm
Location: Romania
Contact:

Post by AndreiCsibi » Mon Sep 01, 2003 8:57 pm

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.

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

Post by Dreamer#1 » Wed Jan 14, 2004 4:13 pm

hi ronaldo,

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

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

Post by CDiMa » Thu Jan 22, 2004 4:50 pm

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

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

Post by Dreamer#1 » Thu Jan 22, 2004 8:36 pm

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...
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

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

Post by Dreamer#1 » Thu Jan 22, 2004 8:41 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? :roll:
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

Post by CDiMa » Fri Jan 23, 2004 11:31 am

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

User avatar
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

Post by cytmike » Thu Jun 24, 2004 3:05 am

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]

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: 10512 A Day in Math-land

Post by CDiMa » Fri Jun 25, 2004 5:58 pm

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

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Sat Jun 26, 2004 2:38 pm

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

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Sat Jun 26, 2004 8:00 pm

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

Post by Observer » Sun Jun 27, 2004 10:14 am

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

Post by helmet » Wed Jul 14, 2004 10:07 am

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

Post by FinalLaugh » Mon Jul 19, 2004 9:01 am

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]

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

10512 Need Help

Post by Rocky » Thu Apr 21, 2005 11:04 am

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

Thank's In Advance
Rocky

Post Reply

Return to “Volume 105 (10500-10599)”