10310 - Dog and Gopher

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

Moderator: Board moderators

JWizard
New poster
Posts: 5
Joined: Mon Jul 01, 2002 4:21 pm
Contact:

10310 - Dog and Gopher

Post by JWizard » Sun Aug 04, 2002 1:02 am

I don't know why I keep getting wrong answer... works fine with all the data I tried....

[c]#include <stdio.h>
#include <math.h>

int main()
{
int n;
double gx, gy, dx, dy;
while(5 == scanf("%d %lf %lf %lf %lf", &n, &gx, &gy, &dx, &dy))
{
int i, j, s = 0;
for(i = 0 ; i < n ; i++)
{
double x, y, dg, dd;
scanf("%lf %lf", &x, &y);
dg = hypot(gx-x, gy-y);
dd = hypot(dx-x, dy-y);
if(dg*2.0 < dd)
{
printf("The gopher can escape through the hole at (%.3f,%.3f).\n", x, y);
s = 1;
break;
}
}
if(!s) printf("The gopher cannot escape.\n");
}
return 0;
} [/c]

While we are on the topic, does anyone have any tips for finding "tricky" input ? :)

Thanks

Hauser
New poster
Posts: 4
Joined: Tue Aug 13, 2002 7:32 pm

Post by Hauser » Tue Aug 13, 2002 7:41 pm

I've used long longs, not doubles, and I've got AC.
(You can simply operate on numbers multiplied by 1000).
Also, you don't have to use sqrt function, or something. You can simply
compare squares of numbers.


Hauser

seolv
New poster
Posts: 11
Joined: Wed Oct 24, 2001 2:00 am

Post by seolv » Sat Aug 17, 2002 9:35 am

I tried to solve this problem too but I got WA.

I think,, the solution of this problem is obvious and the reason why i got WA is something related floating number arithmatics.

I changed double to long datatype but it doesn't work. --;

Do you know any good sites that explain floating number errors?

plz answer me

Hauser
New poster
Posts: 4
Joined: Tue Aug 13, 2002 7:32 pm

Post by Hauser » Sat Aug 17, 2002 7:54 pm

I haven't check if 'long' is enough, but I've used instead 'long long'
(it is 64bit integer, 2x bigger than normal long which is 32bit), and I got AC.

Some parts of my program:

[c]
long long dog_x, dog_y;
long long gopher_x, gopher_y;

int can_escape( long long x, long long y)
{

long long dog_l, gopher_l;

dog_l = (x-dog_x)*(x-dog_x) + (y-dog_y)*(y-dog_y);
gopher_l = (x-gopher_x)*(x-gopher_x) + (y-gopher_y)*(y-gopher_y);

if( 4*gopher_l <= dog_l )
return 1;
else
return 0;

}
[/c]


When reading numbers from input, you should multiply them by 1000.
To read a number I've used this function:

[c]int get_spaces(void)
{
int c;
while( isspace(c=getchar()) );
ungetc( c, stdin );
return c;
}

long long get_number(void)
{
int c;
int minus=1;
int i;
long long result = 0;
c=get_spaces();


if( c=='-' ) {
minus = -1;
getchar();
}

while( (c=getchar())!=' ' && c!='.') {
result *= 10;
result += c-'0';
}

if( c==' ' )
return minus*result*1000;

for( i=0; i<3; i++ ) {
c=getchar();
if( c==' ' )
break;

result *= 10;
result += c-'0';
}

while( i<3 ) {
result *= 10;
i++;
}

return minus*result;
}[/c]

I think it can be done much easier, but thats the way i've done it.
You should also use some yours printing method.

Hauser

Johnny_T
New poster
Posts: 2
Joined: Fri Sep 27, 2002 2:30 am

Why the possible Wrong Answer

Post by Johnny_T » Fri Sep 27, 2002 2:32 am

Apparently if the gopher reaches the hole at the same time as the dog it is considered that he escapes...

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

Re:

Post by scythe » Tue Oct 08, 2002 5:07 pm

This is easier:
[c]
scanf("%d.%d", &a, &b);
x = (long long) (a * 1000 + b);
[/c]

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

Sorry

Post by scythe » Wed Oct 09, 2002 5:06 pm

Sorry, that wouldnt work for negative numbers
Still, i got ac using double data type and an 1e-7 epsilon.

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

10310...WA

Post by SilVer DirectXer » Sun Apr 13, 2003 6:34 am

i have tested many cases and i cant see any errors..
[cpp]
#include <iostream.h>
#include <stdio.h>
#include <math.h>
class co{
public:
double x;
double y;
};
co dog, g,holes[1003];
int pts;
int i,j,k;
double dd,dg;
int a;
int gx,gy,hx,hy,dx,dy;
void main(void)
{
while (1)
{
cin>>pts;
if (cin.eof())
break;
cin>>g.x;
cin>>g.y;
gx=g.x*1000;
gy=g.y *1000;
cin>>dog.x;
cin>>dog.y;
dx=dog.x*1000;
dy=dog.y*1000;


for (i=0;i<pts;i++)
{
cin>>holes.x >>holes.y ;
}
for (i=0;i<pts;i++)
{
hx=holes.x *1000;
hy=holes.y *1000;

dd=(dx-hx)*(dx-hx)+(dy-hy)*(dy-hy) ;
dd=sqrt(dd);
dd/=2;

dg=(gx-hx)*(gx-hx )+(gy-hy )*(gy-hy );
dg=sqrt(dg);

a=0;
if (dd>dg)
{
a=1;
printf("The gopher can escape through the hole at (%.3f,%.3f).\n",holes.x ,holes.y );
break;
}

}
if (a==0)
cout<<"The gopher cannot escape."<<endl;
}


}
[/cpp]

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Sun Apr 20, 2003 6:18 pm

have you try

if (dd>=dg)


notice the '=' there.

beska
New poster
Posts: 2
Joined: Thu Mar 13, 2003 2:10 am

I dunno...

Post by beska » Tue Apr 22, 2003 9:41 pm

I think I'm having the same problem, though I'm using Java. I'm getting WA, even though the algorithm seems obvious. I am checking for >= rather than strictly >, so that's not the issue... Any bizzare test cases people have would help.[/java]

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Wed Apr 23, 2003 4:28 pm

when I first submit I use '>'
and get Wa, when I changed it
to '>=' then I get Ac

I use double to solve this using C

FlareCDE
New poster
Posts: 3
Joined: Fri Mar 21, 2003 6:31 pm
Location: New York
Contact:

Post by FlareCDE » Wed Apr 23, 2003 10:36 pm

A few things I noticed. You need to check for equals, as posted above. Doubles seem to help, my floats gave me WA. Another big thing is to watch for integer division in c++. dogDist/2 gives a WA, but dogDist/2.0 does not :). Be careful there, this one is simple but a few minor programming nuances can really mess it up.
- Flare Araxion

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Wed Apr 23, 2003 11:19 pm

For problems like this, logically, it's straightforward to solve using floating-points operations (i.e.: using doubles). But, if you're skeptical about it because of precision stuff ... use integer operation. I think this problem is very doable using integer operation ... (e.g.: multiply the input numbers with 1000 ... or something like that).

My AC-ed solution is using double, though ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

math is always important...

Post by stcheung » Mon May 19, 2003 11:28 am

People, perhaps this may be the most useful tip on getting your 10310 program to AC. First of all, you can use doubles (no need to use long long and multiply input by 1000 blahblah). Secondly, when the dog & gopher reach the hole at same time, it's still considered a successful escape. Lastly, and definitely NOT the least, if you are lazy like me and didn't take sqrt when calculating distances, then when you compare the dog & gopher distances, remember to multiply gopher distance by 4 (or divide dog distance by 4). Multiplying/dividing by 2 doesn't work if you HAVE NOT taken square root (and that's how I keep getting WA at first).

~Sunny

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

10310 - Dog and Gopher

Post by bugzpodder » Sat Sep 20, 2003 4:06 am

I have:
1) made the output precision to 3 decimal places
2) output the first available hole and ignored all the ones after inputting them
3) if dog and gopher reaches a hole at the same time, gopher escapes
4) used long long to avoid any precision error (including not taking sqrt and using 4 to replace 2 upon squaring)

but i still cannot get the problem. please help!!

[cpp]

#include<iostream>
#include<cmath>
#include<iomanip>
//#include<fstream>
using namespace std;

long long dist(long long a, long long b){
return a*a+b*b;
}


int main(){
long long d1,d2,gx,gy,dx,dy,hx,hy;
int N,i;
double dgx,dgy,ddx,ddy,dhx,dhy;
bool flag;

while(cin>>N>>dgx>>dgy>>ddx>>ddy){
gx=(long long)(dgx*1000ULL); gy=(long long)(dgy*1000ULL);
dx=(long long)(ddx*1000ULL); dy=(long long)(ddy*1000ULL);
flag=false;
for (i=0;i<N;i++){
cin>>dhx>>dhy;
if (flag) continue;
hx=(long long)(dhx*1000ULL); hy=(long long)(dhy*1000ULL);
d1=dist(hx-dx,hy-dy);
d2=(4ULL)*dist(hx-gx,hy-gy);
if (d1>=d2){
flag=true;
cout<<"The gopher can escape through the hole at (";
cout<<setiosflags(ios::fixed)<<setprecision(3)<<dhx<<","<<dhy<<")."

<<endl;
}
}
if (!flag) cout<<"The gopher cannot escape."<<endl;
}
return 0;
}[/cpp]
Last edited by bugzpodder on Tue Sep 23, 2003 12:54 am, edited 1 time in total.

Post Reply

Return to “Volume 103 (10300-10399)”