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 [i].x, t [i].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 [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

[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][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

[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[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;
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[i],y[i]);
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[i],y[i]);
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[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!!!