10610 - Gopher and Hawks

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

Moderator: Board moderators

rasel04
New poster
Posts: 9
Joined: Sun Dec 07, 2003 4:52 am

10610 - Gopher & Hawks

Post by rasel04 » Tue Mar 30, 2004 11:34 pm

I use the following procedure:

1. mark all (u,v) such that gopher can go from u to v in m minutes with its speed v m/sec.

2.Then call bfs.

But get wrong ans. Is the procedure wrong?

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

Post by shamim » Wed Mar 31, 2004 6:11 am

Yes, this is the correct procedure.
perhaps your program does not work for special cases or you are making spelling mistakes.

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Thu May 06, 2004 3:40 pm

Why does this get WA, I'm going sligtly mad ...

[pascal]

program miazio;

const
max = 10000;

{}

function odl (ax, ay, bx, by:real):real;
begin

odl:=sqrt (sqr (ax - bx) + sqr (ay - by));

end;

{}

type mia = record
x, y:real;
end;

var
t:array [1..max] of mia;
kro:array [1..max] of longint;
kolej:array [1..max] of longint;
v, mp, pysk, ogon:longint;
d, i, j, k, l:longint;
m:real;
nmwk1, nmwk2, rea:boolean;

{}

begin

repeat

readln (v, mp);
if (v = 0) and (mp = 0) then exit;

m:=v * 60 * mp;
i:=0;

while not eoln do
begin

inc (i);
read (t .x, t .y);
if eoln then readln;
if eoln then break;

end;

j:=i;
kolej [1]:=1;
ogon:=0;
pysk:=1;
rea:=false;

for i:=1 to max do
kro :=10000;

while (ogon <> pysk) and (rea = false) do
begin

inc (ogon);

for i:=2 to j do
if (i <> kolej [ogon]) and (odl (t [kolej [ogon]].x, t [kolej [ogon]].y, t .x, t .y) < m) then
if kro = 0 then

begin

inc (pysk);
if i = 2 then rea:=true;
kolej [pysk]:=i;
if i <> 1 then
if (kro > kro [kolej [ogon]] + 1) then
kro :=kro [kolej [ogon]] + 1;

end;

end;

if rea then writeln ('Yes, visiting ', kro [2] - 1, ' other holes.') else
writeln ('No.');

until eof;

end.

[/pascal]

Any ideas? Plz help ;)
kiha

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos » Tue Jun 29, 2004 11:53 pm

I use the following procedure

1.- it creates the graph
2.- use algorithms Dijkstra or Lee,

[c]

int lee(int des){
short int r = -1, i, j, in = 0, fin = 0 , x;
d[fin] = 0; cola[fin++] = 0;
v[0] = 1;
while(in < fin && r < 0){
x = cola[in];
for(i=0;i<ng[x];i++)
if(!v[g[x]]){
j = g[x];
if(j == des){ r = d[in]+1; break;}
cola[fin] = j;
d[fin] = d[in]+1;
v[j] = 1;
fin++;
}
in++;
}
return r;
}


main(){
---
/*0 is initial hole
1 is teminal hole
*/
holes = lee(1);
if(holes < 0) printf("No.\n");
else printf("Yes, visiting %d other holes.\n", holes-1);
---
}
[/c]

and AC :D

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sat Jul 03, 2004 7:37 pm

I use BFS and get WA very many times.I can't find my error.May be there are some spacial cases ,please,give me some test cases.
This is my code.
[pascal]var x,y:array[0..1100] of real;
s:array[0..1100] of longint;
i,j,k,n,v,m:longint;
xs,ys,rr:real;
procedure solve;
var i,j,k:longint;
f:boolean;
begin
for i:=1 to n do
s:=0;
k:=1;
s[1]:=1;
repeat
f:=true;
for i:=1 to n do
if s=k then
for j:=1 to n do
if i<>j then
begin
rr:=sqrt(sqr(x-x[j])+sqr(y-y[j]));
if (rr<=m*60*v) and (s[j]=0) then
begin
s[j]:=k+1;
f:=false;
end;
end;
k:=k+1;
until (f=true) or (s[n]<>0);
end;
begin
repeat
for i:=1 to 1000 do
begin
x:=0;y:=0;s:=0;
end;
readln(v,m);
if (v=0) and (m=0) then break;
readln(x[1],y[1]);
readln(xs,ys);
j:=0;
i:=1;
while not eoln do
begin
i:=i+1;
read(x,y);
if eoln then readln;
if eoln then break;
end;
n:=i+1;
x[n]:=xs;
y[n]:=ys;
solve;
if s[n]=0 then writeln('No.') else
writeln('Yes, visiting ',s[n]-2,' other holes.');
until (m=0) and (v=0);
end.
[/pascal]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sun Jul 04, 2004 12:11 pm

I can't find my mistake.
I can't understand why I'm getting WA.
I get WA with BFS;TLE with FLoyd and WA with Deikstra. :(
May be i'm doing something wrong when read the coordinates.Please help me. :cry:
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sun Jul 04, 2004 6:43 pm

Finaly i find my mistake and got AC. :D
I was making mistake while reading. :D
I got AC with BFS.But WA with Diejkstra. :D
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

So what was your mistake?

Post by medv » Mon Jul 19, 2004 5:49 pm

So what was your mistake?
I have also WA. Probably it will help me.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Mon Jul 19, 2004 7:30 pm

If you are writing by pascal then i can tell you my mistake.I make mistake when read the coordinats. You must do it like this.
[pascal]
i:=0;
while not eoln do
begin
i:=i+1;
readln(x,y);
end;
[/pascal]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Fri Aug 13, 2004 11:01 am

Hello Kiha... !!

I have just got Ac with this task....
Don't use strings... (i.e. procedure lam) use simply reals.

< Nie wczytuj stringow tylko od razu wczytuj dwa reale... tak ja robilem i dostalem AC... >
Remember Never Give Up
Regrads
Miras

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10610 - WA! Why Dejkstra does not work???

Post by medv » Wed Sep 01, 2004 11:46 pm

Could smb help me?
Why Dejkstra does not work???
Give me some tests!

program p10610;
const
MAX = 1002;
var
g:array[0..MAX+1,0..MAX+1] of double;
d,x,y:array[0..MAX+1] of double;
Holes,w,v,m,i,j:integer;
min,di,DIST:double;
s:array[0..MAX+1] of boolean;
pi:array[0..MAX+1] of integer;

function minimum(i,j:double):double;
begin
if i<j then minimum := i
else minimum := j;
end;

begin
while True do
begin
readln(v,m);
if v + m = 0 then break;
DIST := v * m * 60; {max distance to run not to be eaten}
readln(x[0],y[0]);
readln(x[1],y[1]);
Holes := 1;
while not eoln do
begin
Inc(Holes);
readln(x[Holes],y[Holes]);
end;
for i:=0 to Holes do for j:=0 to Holes do
if i=j then g[i,j] := 0 else g[i,j] := MAXLONGINT;
for i:=0 to Holes do
for j:=0 to Holes do
if i <> j then
begin
di := sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
if di <= DIST then begin g[i,j] := di; g[j,i] := di; end;
end;

for i:=0 to Holes do d[i] := g[0,i];
FillChar(s,sizeof(s),0);
d[0] := 0; s[0] := True;
FillChar(pi,sizeof(pi),0);
for j := 1 to Holes do
begin
min := MAXLONGINT;
for i:= 0 to Holes do
if ((not s[i]) and (d[i] < min)) then
begin
min := d[i]; w := i;
end;
for i:=0 to Holes do
if (not s[i]) then
if d[w] + g[w,i] < d[i] then
begin
d[i] := d[w] + g[w,i]; pi[i] := w;
end;
s[w] := True;
end;

if d[1] < MAXLONGINT then
begin
i := 1; j := 0;
while pi[i] <> 0 do
begin
i := pi[i]; Inc(j);
end;
writeln('Yes, visiting ',j,' other holes.');
end else writeln('No.');
end;
end.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sun Jul 15, 2007 9:57 pm

I have used DFS approach with DP . I have absolute no idea why I am getting TLE . Is there anything wrong in my input taking or the algo is too slow?? I found in this forum that people used BFS to have solved this problem.So, using DFS would not be algorithmically slower.

here is my code ..

Code: Select all

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>

#define INF 99999

using namespace std;

class point
{
public:
	double x,y;
};

point P[1010];
char s[100];
int count;//number of points
double con;//condition to be satisfied
bool used[1010];//used marker
int d[3010];//memo

double dis(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int search(int p,bool used[])
{
	if(p==1)
	{
		d[p]=1;
		return 1;
	}
	if(d[p]<INF)
	{
		return d[p];
	}
	register int min=INF,i,x;
	for(i=0;i<count;i++)
	{
		if(!used[i] && dis(P[p],P[i])<=con)
		{
			used[i]=true;
			x=1+search(i,used);
			if(x<min)
			{
				min=x;
			}
			used[i]=false;
		}		
	}
	d[p]=min;
	return min;
}
int main(void)
{
	register double v,t;
	register char dummy[10];
	while(1)
	{
		scanf("%lf%lf",&v,&t);
		if(v==0 && t==0)
		{
			break;
		}
		else 
		{
			con=v*t*60.0;
		}
		gets(dummy);
		count=0;
		while(1)
		{
			gets(s);
			if(strcmp(s,"")==0)
			{
				break;
			}
			sscanf(s,"%lf%lf",&P[count].x,&P[count].y);
			d[count]=INF;
			used[count]=false;
			count++;
		}		
	
		used[0]=true;
		register int x=search(0,used);
		if(x<INF)
		{
			printf("Yes, visiting %d other holes.\n",x-2);
		}
		else
		{
			printf("no.\n");
		}
	}
	return 0;
}
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

sushil2006090
New poster
Posts: 7
Joined: Wed Feb 20, 2008 3:17 pm
Contact:

Re: 10610 - Gopher and Hawks

Post by sushil2006090 » Fri Feb 13, 2009 4:15 pm

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<queue>

using namespace std;
struct point
{
double x,y;
};
int main()
{
double speed, tim;
cin>>speed>>tim;
while(speed!=0 && tim!=0)
{
tim*=60.0000000;
vector<point>v;
double maxi=tim*speed;
maxi*=maxi;
point start,target;
cin>>start.x>>start.y>>target.x>>target.y;
v.push_back(start);
v.push_back(target);
double x,y;
string str;
getline(cin,str);
while(true)
{
getline(cin,str);
if(str.size()==0) break;
stringstream ss(str);
ss>>x>>y;
point p1; p1.x=x; p1.y=y;
v.push_back(p1);
}

int len=v.size();
bool mat[len][len];
memset(mat,false,sizeof(len));
int mem[len];
memset(mem,0,sizeof(mem));

for(int i=0;i<len;i++)
{
for(int j=i+1;j<len;j++)
{
double dist=pow((v.x-v[j].x),2.0) + pow((v.y-v[j].y),2.0);
if(maxi-dist>=0.00000)
{
mat[j]=true;
mat[j]=true;
}
}
}

/* for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
{
cout<<mat[j]<<" ";
}
cout<<endl;
}*/

queue<int>Q;
Q.push(0);

int ret=-1;

while(!Q.empty())
{
int temp=Q.front();
Q.pop();
if(temp==1){ ret=temp; break;}

for(int i=0;i<len;i++)
{
if(mat[temp]==true && mem==0)
{
Q.push(i);
mem=mem[temp]+1;
}
}
}

if(ret==-1) cout<<"No.\n";
else
{
cout<<"Yes, visiting "<<mem[ret]-1<<" other holes.\n";

}
cin>>speed>>tim;

v.clear();
}
system("pause");
}



could sm1 xplain to me whats the problem in this code
here is the algo that i have used......

1)made a bool matrix based on the distance between the two points i.e if the point is close then 1 otherwise 0
2) used the bfs to move from the start to target point. if the queue is emptied b4 reaching then we have not found the target so ans is "No" otherwise i have stored the number of steps which has been used to reach to that point...

ny suggestion regarding the query will be xtremely helpful!!!

User avatar
outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

10610 - Gopher and Hawks

Post by outsbook » Mon Nov 28, 2011 4:57 pm

BFS problem

This is just a BFS problem with a bit of math.
1. Find all adjacency using this condition, consider two holes connected if the distance between them is less than or equal to v*m*60.
2. Run BFS on the gopher holes to destination hole.
3. If gopher reach to destination hole then print length of shortest path -1.
4. Otherwise print No.

try this

Code: Select all

The input/output is incorrect so it has been removed.
Please see https://www.udebug.com/UVa/10610 instead.
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10610 - Gopher and Hawks

Post by Mukit Chowdhury » Sat Sep 14, 2013 5:40 am

Accepted ... :D

Post Reply

Return to “Volume 106 (10600-10699)”