10964 - Strange Planet

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

10964 - Strange Planet

Post by Antonio Ocampo » Tue Nov 15, 2005 4:19 am

Hi for all. I got WA in this problem :cry: . Could someone confirm this I/O or sharing with me another one?


Input

Code: Select all

1 1
3423 345223
564 1231
873 123
856 43
99 11
100000000 198437
87584 28323
9999913 762
1000000000 1000000000
0 0
9826 32
9567 823
-1 -1
Output

Code: Select all

0.00
339.91
5.83
9.85
13.34
7.00
5221.20
234.92
1809.24
0.00
0.00
47.71
38.90
Thx in advance :wink:

intergalactic
New poster
Posts: 2
Joined: Fri Nov 11, 2005 7:20 pm

Post by intergalactic » Tue Nov 15, 2005 4:50 am

My AC program produces the following result

Code: Select all

0.00
339.91
5.83
9.85
13.34
7.00
5221.20
234.92
1810.20
0.00
0.00
47.71
38.90


Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Wed Nov 16, 2005 6:13 am

Uhmmmmmmm I got a different output for

Code: Select all

9999913 762 
Now my question is WHY? :roll: I guess i'm using a right approach. Could anyone give me any critical I/O?

Regards :P

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Nov 16, 2005 12:01 pm

Did you try to debug the (x,y) positions you calculate for all small values? I guess that should help.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Wed Nov 16, 2005 5:15 pm

Thx for your reply Adrian. I've fixed a little mistake in my code :D However, I still get WA :cry:

Could you or someone else give me the outputs for these inputs?


Input

Code: Select all

123 1423
57 234
6723 546
733 785143
98743 12
2 43
16 852
7653 34
42 98
564 111
9999999 23
10000001 1000000000
1000 10000
871 2387
67676 2435
99999 99999
62 66565
0 1
1 0
-1 -1
Output

Code: Select all

17.80
12.08
68.07
518.19
181.73
4.24
14.14
44.65
10.20
17.49
1739.94
1737.59
72.01
38.21
129.71
0.00
139.86
1.00
1.00
Thx in advance :P

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Nov 16, 2005 7:55 pm

For:
10000001 1000000000
I get:
18467.79
(one point is at (1627, -609), the other at (-6281, 16080) ).

for all other values I get the same output.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Nov 17, 2005 4:03 am

Might the problem be integer overflow?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Thu Nov 17, 2005 9:58 pm

Thx a lot Adrian and Observer !!!!!!!!!! I've finally got AC :P It was an integer overflow error :oops:

Thx again and keep posting.

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » Thu Nov 24, 2005 6:44 pm

I can't figure out the formula. Even I don't know, is there any stright forward formula exist or not. Plz give me some hints. Thanks in advance.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Location: Hyderabad
Contact:

Post by sandy007smarty » Thu Apr 20, 2006 7:11 pm

My code is working for all the above test cases provided above in the variuos posts. But still I m getting WA. I thought may be uva's compiler uses 2 bytes for int and then changed datatype to even long int and then to even long long. Still getting WA. plz help.

Code: Select all

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<long long,long long> pt;
pt findCartesian(long long a)
{
        if(a==0)
                return make_pair(0,0);
        long long n,x,y,b,dx=1,dy=-1;
        n=(long long)sqrt(1.0f*a/2);
        while(2*n*(n-1)<a)
                n++;
        b=2*n*(n-1);
        x=-1*(n-1);
        y=0;
        while(b!=a)
        {
                x=x+dx;
                y=y+dy;
                if(y==0)
                        dx=-1*dx;
                if(x==0)
                        dy=-1*dy;
                b--;
        }
        return make_pair(x,y);
}
int main()
{
        long long a,b;
        float ans;
        pt pt1,pt2;
        while(1)
        {
                scanf(" %lld%lld",&a,&b);
                if(a==-1&&b==-1)
                        break;
                pt1=findCartesian(a);
                pt2=findCartesian(b);
//              cout<<"("<<pt1.first<<","<<pt1.second<<") ("<<pt2.first<<","<<pt2.second<<")\n";
                ans = sqrt((pt1.first-pt2.first)*(pt1.first-pt2.first)+(pt1.second-pt2.second)*(pt1.second-pt2.second));
                printf("%.2f\n",ans);
        }
        return 0;
}

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Location: Hyderabad
Contact:

got AC but doubts

Post by sandy007smarty » Sun Apr 23, 2006 9:29 am

I got AC when i changed the variable ans from float to double. Still I don't understand how does that effect the answers as the precison required is only 2 digits after the decimal point. Any idea?

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Tue Apr 25, 2006 6:19 pm

Of course it needs 2 digit, but float is not big enough to hold the result.
In acm you should always use double instead of float.

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Location: Hyderabad
Contact:

Post by sandy007smarty » Sun Apr 08, 2007 7:50 pm

Thanx. I am already following it now.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10964 - Strange Planet

Post by DD » Sun Feb 24, 2013 11:04 pm

Just wondering that brute-force simulation can passed this or not although I use the algorithm almost used by everyone on this :roll:
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 109 (10900-10999)”