10610 - Gopher and Hawks

Moderator: Board moderators

10610 - Gopher & Hawks

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?
rasel04
New poster

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

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

shamim
A great helper

Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Dhaka

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

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

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

while not eoln do
begin

inc (i);
if eoln then break;

end;

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

for i:=1 to max do
kro [i]:=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 [i].x, t [i].y) < m) then
if kro [i] = 0 then

begin

inc (pysk);
if i = 2 then rea:=true;
kolej [pysk]:=i;
if i <> 1 then
if (kro [i] > kro [kolej [ogon]] + 1) then
kro [i]:=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
kiha
New poster

Posts: 37
Joined: Sat Dec 20, 2003 10:59 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][i]]){
j = g[x][i];
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

lord_burgos
New poster

Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico

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[i]:=0;
k:=1;
s[1]:=1;
repeat
f:=true;
for i:=1 to n do
if s[i]=k then
for j:=1 to n do
if i<>j then
begin
rr:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-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[i]:=0;y[i]:=0;s[i]:=0;
end;
if (v=0) and (m=0) then break;
j:=0;
i:=1;
while not eoln do
begin
i:=i+1;
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

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

Finaly i find my mistake and got AC.
I was making mistake while reading.
I got AC with BFS.But WA with Diejkstra.
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

I have also WA. Probably it will help me.
medv
Learning poster

Posts: 85
Joined: Sun Jul 14, 2002 1:17 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;
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

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
Miras
miras
Learning poster

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

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

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
if v + m = 0 then break;
DIST := v * m * 60; {max distance to run not to be eaten}
Holes := 1;
while not eoln do
begin
Inc(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.
medv
Learning poster

Posts: 85
Joined: Sun Jul 14, 2002 1:17 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 99999using namespace std;class point{public:   double x,y;};point P[1010];char s[100];int count;//number of pointsdouble con;//condition to be satisfiedbool used[1010];//used markerint d[3010];//memodouble 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

Kallol
Learning poster

Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Re: 10610 - Gopher and Hawks

#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[i].x-v[j].x),2.0) + pow((v[i].y-v[j].y),2.0);
if(maxi-dist>=0.00000)
{
mat[i][j]=true;
mat[j][i]=true;
}
}
}

/* for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
{
cout<<mat[i][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][i]==true && mem[i]==0)
{
Q.push(i);
mem[i]=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!!!
sushil2006090
New poster

Posts: 7
Joined: Wed Feb 20, 2008 3:17 pm

Previous