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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 10310: vague problem statement

Post by helloneo » Tue Jan 17, 2006 3:39 am

shadow wrote:The problem hasnt precisely defined the answer when the dog and the gopher both reach a hole at the same time. I think the answer in this case is "can reach".
you're right..

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Mon Feb 06, 2006 8:27 pm

so... if both reaches a role at same time, the dog eats the gopher...
that's right???

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Tue Feb 07, 2006 3:18 am

beloni wrote:so... if both reaches a role at same time, the dog eats the gopher...
that's right???
that case.. the gopher is safe..

isagooddaytodie
New poster
Posts: 3
Joined: Tue Mar 13, 2007 11:04 am
Contact:

Re: math is always important...

Post by isagooddaytodie » Tue Apr 24, 2007 6:42 am

stcheung wrote: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
And don't forget them outputs, oh boy do that thing blows up if you don't make it a 3 decimal pecision exact.

Itachi-Forsaken
New poster
Posts: 10
Joined: Mon May 07, 2007 4:45 am

Post by Itachi-Forsaken » Wed May 23, 2007 11:29 pm

Hi I'm trying to do this problem since the algorithm is straight forward but I can't AC for some reason so I was wondering if someone could kindly help me find the bugs in code =)

Here it is..hope someone can tell me what's wrong with it

Code: Select all

#include<iostream>
#include<stdio.h>
using namespace std;

typedef struct
{
        double x, y;
}point;

inline double sqr(double n) { return n*n; }

int main()
{
    while( !cin.eof() )
    {
         point dog, gopher;
         int nholes, i, flag=0;
         point hole, escape;
         cin>>nholes;
         cin>>gopher.x>>gopher.y>>dog.x>>dog.y;
         for( i=0; i<nholes; i++ )
         {
              cin>>hole.x>>hole.y;
              if( flag==1 ) continue;
              
              if( (sqr(hole.x-dog.x)+sqr(hole.y-dog.y))>=4.0*(sqr(hole.x-gopher.x)+sqr(hole.y-gopher.y)) )
              {    
                  escape.x=hole.x; escape.y=hole.y;
                  flag=1;
              }
         }
         if( flag==0 )
             printf("The gopher cannot escape.\n");
         else
             printf("The gopher can escape through the hole at (%.3lf,%.3lf).\n", escape.x, escape.y);
    }
    return 0;
}
    

yangmie
New poster
Posts: 3
Joined: Fri Nov 30, 2007 12:14 pm
Contact:

Post by yangmie » Wed Dec 05, 2007 7:19 am

#include<stdio.h>
#include<math.h>
int main()
{
int n,k,temp;
double x1,y1,x2,y2;
double holeX[10000],holeY[10000];
double d1,d2;
while(scanf("%d%lf%lf%lf%lf",&n,&x1,&y1,&x2,&y2)==5)
{
temp=0;
for(k=0;k<n;k++)
{
scanf("%lf%lf",&holeX[k],&holeY[k]);
d1=sqrt((holeX[k]-x1)*(holeX[k]-x1)+(holeY[k]-y1)*(holeY[k]-y1));
d2=sqrt((holeX[k]-x2)*(holeX[k]-x2)+(holeY[k]-y2)*(holeY[k]-y2));
if(2*d1<=d2)
{
printf("The gopher can escape through the hole at (%.3lf,%.3lf).\n",holeX[k],holeY[k]);
temp=1;
break;
}
}
if(temp==0)printf("The gopher cannot escape.\n") ;
}
return 0;
}



why i got wa......?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Dec 05, 2007 11:36 am

Try this:

Code: Select all

3 2.000 2.000 1.000 1.000
2.500 2.500
1.500 1.500
0.000 0.000
-----
Rio

cyclops_kun
New poster
Posts: 4
Joined: Mon Dec 08, 2008 11:03 am

I got AC in UVa judge, but i got WA in Programming-challenge

Post by cyclops_kun » Mon Dec 08, 2008 11:25 am

Please Help..
I got AC in UVa judge, but why i got WA in http://www.programming-challenges.com judge? I don't understand..
I'm sorry posting my AC code here :-? , but, for me it's still WA :o , coz it's WA in programming-challenges, please help..thanks in advance.. :)

Here is my code, for anyone who got AC, please try at http://www.programming-challenges.com and please tell me why i got WA there?

Code: Select all

#include<iostream>
#include<iomanip>
#include<cmath>
#define eps 1e-7

using namespace std;

double panjang(double x1, double y1, double x2, double y2);

int main()
{
    int n;
    double G1, G2, D1, D2;
    double H[1000][2];
    int i, check;
    
    cout<<fixed<<showpoint<<setprecision(3);
    while(cin>>n>>G1>>G2>>D1>>D2)
    {
    check=0;
    for(i=0; i<n; i++)
        cin>>H[i][0]>>H[i][1];
    for(i=0; i<n; i++)
    {
        if(panjang(D1,D2,H[i][0],H[i][1])>2*panjang(G1,G2,H[i][0],H[i][1]))
        {
          cout<<"The gopher can escape through the hole at ("<<H[i][0]+eps<<","<<H[i][1]+eps<<")."<<endl;
          check++;
          break;
        }
    }
    if(check==0)
       cout<<"The gopher cannot escape."<<endl;
    }
    return 0;
}
double panjang(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));    
}

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

10310 - Dog and Gopher

Post by sazzadcsedu » Thu Jan 29, 2009 9:45 pm

whats wrong with my code??

Code: Select all

              #include<stdio.h>
             #include<math.h>
             #include<stdlib.h>

              #define eps 1e-7

              double h[1001][1001];
       
               int main()



			   { 

				  
				   int nhole,i,flag;
			
				   double x1,x2,y1,y2,dis_gof,dis_dog,h_x,h_y;

				    

				  // freopen("input.txt","r",stdin);
				  //freopen("output.txt","w",stdout);

				   while(scanf("%d",&nhole)==1)

				   { 
                     
					   //sscanf(str,"%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
				   scanf("%lf %lf %lf %lf\n",&x1,&y1,&x2,&y2);
               
				     for(i=0;i<nhole;i++)

					 { 
						 

						 scanf("%lf %lf",&h_x,&h_y);
						 
						 //h_x=atof(str1);
						 //h_y=atof(str2);
						 

				dis_gof=(((x1-h_x)*(x1-h_x))+((y1-h_y)*(y1-h_y)));
				printf("%lf\n",dis_gof);
                dis_dog=((x2-h_x)*(x2-h_x))+((y2-h_y)*(y2-h_y));
 
                printf("%lf\n",dis_dog);

				   if(dis_dog-4*dis_gof>=eps)
				
				   {  
                     
					 

					   flag=1;
				        break;
                   
				   }
				   else
				
				   { 
					 

					 
				    
					   flag=0; 
					   
				   }
                      scanf("\n");
					    

					 }

					 //printf("flag=%d\n",flag);
                     
				  	 if(flag==1)
				     printf("The gopher can escape through the hole at (%.3lf,%.3lf).\n",h_x,h_y);
                     
					 else
						 printf("The gopher cannot escape.\n");
					 

				   }
				   return 0;

			   }



	
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 10310 - Dog and Gopher

Post by newkid » Fri Jan 30, 2009 9:46 pm

@sazzadcsedu
you are breaking the "for(i=0;i<nhole;i++)" loop if you find a suitable hole for the gopher. this loop happens to do the scanning as well "scanf("%lf %lf",&h_x,&h_y);". now tell me what will happen if you find a suitable hole before scanning all the hole co-ordinates? I mean say nhole is 10 and the 2nd hole is a escape hole for the gopher..
hmm..

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10310 - Dog and Gopher

Post by sazzadcsedu » Fri Jan 30, 2009 11:38 pm

NEWKID,
IF NOT BREAK THE LOOP
THEN IT PRINT THE LAST ESCAPABLE HOLE.
IF MORE THEN 1 ESCAPABLE HOLE THEN WHAT SHOULD BE ANSWER????
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 10310 - Dog and Gopher

Post by newkid » Fri Jan 30, 2009 11:46 pm

oh.. thats the easy part.. you can do like this..

Code: Select all

typedef struct Hole {
  double x, y;
}
Hole hole[MAXHOLES];
for (int i = 0; i < nholes; i++) {
  scanf("%lf %lf", &hole[i].x, &hole[i].y);
}

for (int i  = 0; i < nholes; i++) {
  //  if feasible with this hole then set ur flag and break..
}
hmm..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10310 - Dog and Gopher

Post by Obaida » Tue Feb 03, 2009 8:42 am

Can some one help me. I got TLE.. :o

Code: Select all

removed
Last edited by Obaida on Tue Feb 03, 2009 9:13 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 10310 - Dog and Gopher

Post by newkid » Tue Feb 03, 2009 8:53 am

whats the logic behind this line?

Code: Select all

if(((dog_x>=gophar_x)&&(gophar_x>=hole_x[i]))||((dog_x<=gophar_x)&&(gophar_x<=hole_x[i]))||((dog_x-gophar_x==0)&&(((dog_y>=gophar_y)&&(gophar_y>=hole_y[i]))||((dog_y<=gophar_y)&&(gophar_y<=hole_y[i])))))
just comment this line and you will get accepted..
hmm..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10310 - Dog and Gopher

Post by Obaida » Tue Feb 03, 2009 9:12 am

Sorry i was kidding. :oops: :oops: :oops: :oops:
try_try_try_try_&&&_try@try.com
This may be the address of success.

Post Reply

Return to “Volume 103 (10300-10399)”