10610 - Gopher and Hawks
Moderator: Board moderators
10610 - Gopher and Hawks
Hi, I keep getting WA for this problem and I think that my program isn't reading the input well. I tried four different methods to do that (some of them got SIGSEGV (?)) but the program isn't working. Any tips on reading the problem's data in C/C++?
Kuba
Kuba
Re: 10610 - Gopher & Hawks
I also get WA all the time.Kuba12 wrote:Hi, I keep getting WA for this problem and I think that my program isn't reading the input well. I tried four different methods to do that (some of them got SIGSEGV (?)) but the program isn't working. Any tips on reading the problem's data in C/C++?
Kuba
I deal it as a shortest path problem.
What's wrong with my thought?
Could someone give some tricy input/output?
thx in advance
Shortest path
I dont understand what you mean by shortest path.
In short, the term that I would use for this program in Breadth First Search.
Of course it is the same as the shortest path problem with all the weights in the graph as 1.
But then the order is 0(n).
bye
In short, the term that I would use for this program in Breadth First Search.
Of course it is the same as the shortest path problem with all the weights in the graph as 1.
But then the order is 0(n).
bye
Re: Shortest path
I have modified my code from shortest path to BFS.abishek wrote:I dont understand what you mean by shortest path.
In short, the term that I would use for this program in Breadth First Search.
Of course it is the same as the shortest path problem with all the weights in the graph as 1.
But then the order is 0(n).
bye
And still get WA.
Code: Select all
deleted
Thx
![:)](./images/smilies/icon_smile.gif)
Last edited by windows2k on Wed Jan 28, 2004 3:44 pm, edited 1 time in total.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
Bad problem statement!!!
In the problem, there is
After receiving wrong answer judge, I only cared about
presion errors, but fogot array size...
Get one lesson: don't open arrays just as problem stated, if
memory is enough.![:)](./images/smilies/icon_smile.gif)
![:x](./images/smilies/icon_mad.gif)
In the problem, there is
Who knows 1000 doesn't include starting and ending ones!There are not more than 1000 gopher holes ...
After receiving wrong answer judge, I only cared about
presion errors, but fogot array size...
Get one lesson: don't open arrays just as problem stated, if
memory is enough.
![:)](./images/smilies/icon_smile.gif)
Retired from SJTU Accelerator 2004
10610 - Gopher and Hawks
[cpp]Please, what's wrong with this code? Can it be precision errors?
#include <stdio.h>
#define NP 1002
#define dx(a,b) (a)-(b)
#define R(a,b) (a)*(a)+(b)*(b)
#define cango_(r) ((r)<=(l2)?1:0)
#define cango(a,b) cango_(R(dx((a)[0],(b)[0]),dx((a)[1],(b)[1])))
double l2;
int main(int argc, char* argv[])
{
#ifndef ONLINE_JUDGE
close (0); open ("myprog.in", O_RDONLY);
close (1); open ("myprog.out", O_WRONLY | O_CREAT, 0600);
#endif
double ps[2],pt[2],point[NP][2],v,t;//,r,pw[2],l2
register int i,j,k,len;
int go[NP],goe[NP];
bool exit,eend;
char a[101];
while (gets(a)) {
sscanf(a,"%lf %lf",&v,&t);
if(!v && !t) break;
l2 = v*t*60.0000000; l2 = l2*l2;
gets(a);
sscanf(a,"%lf %lf",&ps[0],&ps[1]);
gets(a);
sscanf(a,"%lf %lf",&pt[0],&pt[1]);
exit = false;
eend = false;
if(cango(ps,pt)){
exit = true;
printf("Yes, visiting 0 other holes.\n");
}
len = 0;
while ( gets( a ) && sscanf( a, "%lf %lf",&point[len][0],&point[len][1] ) == 2 ) {
if (exit){
continue;
}
go[len] = cango(ps,point[len]);
goe[len] = cango(pt,point[len]);
if(goe[len] && go[len]){
exit = true;
printf("Yes, visiting 1 other holes.\n");
}
len++;
if(eend) break;
}
if (exit) continue;
len--;
exit = false;
k = 0; i = -1;
while(++i<=len && k < len){
if(go <= k ){
if(i == len){
i =-1;
k++;
}
continue;
}
for(j = 0;j<=len;j++){
if (go[j]) continue;
if(cango(point,point[j])){
go[j] = go+1;
if(goe[j]){
exit = true;
printf("Yes, visiting %d other holes.\n",go[j]);
break;
}
}
}
if(exit) break;
if(i == len){
i =-1;
k++;
}
}
if(!exit)
printf("No.\n");
}
return 0;
}
[/cpp]
10610 Gopher and Hawks WA
Hi,
I'm getting angry with this problem. Could anybody please help me ?
I wrote the program [in Pascal] using the command val. I used 1..10000 array which I zero after every test case -- and I got WA in 0.000 -- this sucks [I apologise for bad word, but I can't express my feelings in another way which can be appreciated by you]. I read that, in Pascal, WA may also mean RE.
I use val command, maybe this got me RE. Could somebody give me a clue?
Thanks in advance[/java]
I'm getting angry with this problem. Could anybody please help me ?
I wrote the program [in Pascal] using the command val. I used 1..10000 array which I zero after every test case -- and I got WA in 0.000 -- this sucks [I apologise for bad word, but I can't express my feelings in another way which can be appreciated by you]. I read that, in Pascal, WA may also mean RE.
I use val command, maybe this got me RE. Could somebody give me a clue?
Thanks in advance[/java]
kiha
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
Right, sorry :|
I create a queue [named kolej in my program -- that means queue in Polish] and an array where I store: how many steps are needed to get to this point [how many holes you must visit to reach this hole -- named kro]. And this is my program :
[pascal]program miazio;
{}
function odl (ax, ay, bx, by:real):real; {tihs function computes a distance between two points defined by their xy coordinates}
begin
odl:=sqrt (sqr (ax - bx) + sqr (ay - by));
end;
{}
procedure lam (var s, s1, s2:string); {this procedure breaks the read string to two smaller ones -- I mean when you have s = '1.0 2.0' this procedure would break it into s1 = '1.0' and s2 = '2.0'}
var
i:longint;
begin
s1:='';
s2:='';
i:=0;
repeat
inc (i);
if s <> ' ' then
s1:=s1 + s ;
until s = ' ';
repeat
inc (i);
if s <> ' ' then
s2:=s2 + s ;
until (s = ' ') or (i = length (s));
end;
{}
type mia = record
x, y:real;
end;
var
t:array [1..10000] of mia;
kro:array [1..10000] of longint;
kolej:array [1..100000] of longint;
v, m, pysk, ogon:longint;
i, j, k, l:longint;
s, s1, s2:string;
d:integer;
rea:boolean;
{}
begin
repeat
readln (v, m);
if (v = 0) and (m = 0) then exit;
m:=m * 60;
i:=0;
s:='grewiuitejldnfsvjgyv';
while (s <> '') and (s <> ' ') do
begin
inc (i);
readln (s);
lam (s, s1, s2);
if (s = '') or (s = ' ') then break;
val (s1, t .x, d); {these are the only two places where I use the val}
val (s2, t .y, d); {procedure -- may it be something wrong with it ?}
end;
j:=i - 1;
kolej [1]:=1;
ogon:=0; {tail of queue}
pysk:=1; {head of queue}
rea:=false;{if rea = false that means the target hasn't been reached yet}
for i:=1 to 10000 do
kro :=0;
while (ogon <> pysk) and (rea = false) do
begin
inc (ogon);
for i:=2 to j do
if odl (t [kolej [ogon]].x, t [kolej [ogon]].y, t .x, t [i].y) / v <= m then
if kro [i] = 0 then
begin
inc (pysk);
if i = 2 then rea:=true;
kolej [pysk]:=i;
if i <> 1 then
kro [i]:=ogon;
end;
end;
if rea then writeln ('Yes, visiting ', kro [2] - 1, ' other holes.') else
writeln ('No.');
until eof;
end.[/pascal]
Could you tell me what may be wrong with it, or at least send me some tricky inputs![:)](./images/smilies/icon_smile.gif)
I create a queue [named kolej in my program -- that means queue in Polish] and an array where I store: how many steps are needed to get to this point [how many holes you must visit to reach this hole -- named kro]. And this is my program :
[pascal]program miazio;
{}
function odl (ax, ay, bx, by:real):real; {tihs function computes a distance between two points defined by their xy coordinates}
begin
odl:=sqrt (sqr (ax - bx) + sqr (ay - by));
end;
{}
procedure lam (var s, s1, s2:string); {this procedure breaks the read string to two smaller ones -- I mean when you have s = '1.0 2.0' this procedure would break it into s1 = '1.0' and s2 = '2.0'}
var
i:longint;
begin
s1:='';
s2:='';
i:=0;
repeat
inc (i);
if s <> ' ' then
s1:=s1 + s ;
until s = ' ';
repeat
inc (i);
if s <> ' ' then
s2:=s2 + s ;
until (s = ' ') or (i = length (s));
end;
{}
type mia = record
x, y:real;
end;
var
t:array [1..10000] of mia;
kro:array [1..10000] of longint;
kolej:array [1..100000] of longint;
v, m, pysk, ogon:longint;
i, j, k, l:longint;
s, s1, s2:string;
d:integer;
rea:boolean;
{}
begin
repeat
readln (v, m);
if (v = 0) and (m = 0) then exit;
m:=m * 60;
i:=0;
s:='grewiuitejldnfsvjgyv';
while (s <> '') and (s <> ' ') do
begin
inc (i);
readln (s);
lam (s, s1, s2);
if (s = '') or (s = ' ') then break;
val (s1, t .x, d); {these are the only two places where I use the val}
val (s2, t .y, d); {procedure -- may it be something wrong with it ?}
end;
j:=i - 1;
kolej [1]:=1;
ogon:=0; {tail of queue}
pysk:=1; {head of queue}
rea:=false;{if rea = false that means the target hasn't been reached yet}
for i:=1 to 10000 do
kro :=0;
while (ogon <> pysk) and (rea = false) do
begin
inc (ogon);
for i:=2 to j do
if odl (t [kolej [ogon]].x, t [kolej [ogon]].y, t .x, t [i].y) / v <= m then
if kro [i] = 0 then
begin
inc (pysk);
if i = 2 then rea:=true;
kolej [pysk]:=i;
if i <> 1 then
kro [i]:=ogon;
end;
end;
if rea then writeln ('Yes, visiting ', kro [2] - 1, ' other holes.') else
writeln ('No.');
until eof;
end.[/pascal]
Could you tell me what may be wrong with it, or at least send me some tricky inputs
![:)](./images/smilies/icon_smile.gif)
kiha
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
Thanks, I changed it, but ... still WA :/
Look:
I inserted a part :
[pascal]
for i:=1 to 100000 do
for j:=1 to 100000 do
for v:=1 to 100000 do
if 1 = 1 then i:=j;
[/pascal]
which should give me TL of course. But I got WA in 0.002 which means it was Runtime Error. What is more, I added this part after using val procedure -- then I got WA. When I put it before val, I got TLE. Any ideas? I'm completely confused.
[Sorry for this, I know it ain't fair]
Look:
I inserted a part :
[pascal]
for i:=1 to 100000 do
for j:=1 to 100000 do
for v:=1 to 100000 do
if 1 = 1 then i:=j;
[/pascal]
which should give me TL of course. But I got WA in 0.002 which means it was Runtime Error. What is more, I added this part after using val procedure -- then I got WA. When I put it before val, I got TLE. Any ideas? I'm completely confused.
[Sorry for this, I know it ain't fair]
kiha