10610 - Gopher and Hawks

[rasel04]

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?

[shamim]

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

[kiha]

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

[lord_burgos]

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

[Eduard]

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]

[Eduard]

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.
Thanks.

[Eduard]

Finaly i find my mistake and got AC.
I was making mistake while reading.
I got AC with BFS.But WA with Diejkstra.

[medv]

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

[Eduard]

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]

[miras]

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

[medv]

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.

[Kallol]

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;
}

[sushil2006090]

#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!!!

[outsbook]

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.

[Mukit Chowdhury]

Accepted ...