10610 - Gopher and Hawks

Kuba12 · Post by **Kuba12** » Tue Jan 27, 2004 4:49 pm

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

windows2k · Post by **windows2k** » Tue Jan 27, 2004 6:03 pm

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 also get WA all the time.
I deal it as a shortest path problem.
What's wrong with my thought?
Could someone give some tricy input/output?
thx in advance

Larry · Post by **Larry** » Tue Jan 27, 2004 6:39 pm

Here's how I read the input in C:

[c]
while ( 2 == scanf("%lf %lf\n", &v, &m )) {
/* do stuff */

while ( gets( a ) && sscanf( a, "%lf %lf\n", &p.x, &p.y ) == 2 )
i++;
/* rest of code.. */
}
[/c]

abishek · Post by **abishek** » Tue Jan 27, 2004 6:50 pm

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

Kuba12 · Post by **Kuba12** » Tue Jan 27, 2004 6:52 pm

thanks, I got AC.

windows2k · Post by **windows2k** » Wed Jan 28, 2004 7:20 am

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

I have modified my code from shortest path to BFS.
And still get WA.

Code: Select all

deleted

Could someone tell me what's wrong with my code.
Thx

Adrian Kuegel · Post by **Adrian Kuegel** » Wed Jan 28, 2004 2:47 pm

There are at most 1000 intermediate holes, but starting hole and target hole doesn't count. So you need to increase your array size from 1000 to 1002 and you will get Accepted

windows2k · Post by **windows2k** » Wed Jan 28, 2004 3:47 pm

Adrian Kuegel wrote:There are at most 1000 intermediate holes, but starting hole and target hole doesn't count. So you need to increase your array size from 1000 to 1002 and you will get Accepted

Thx , I missed the point . Now have got Accepted.
Thx Adrian Kuegel

hujialie · Post by **hujialie** » Sat Jan 31, 2004 5:29 pm

Bad problem statement!!!

In the problem, there is

There are not more than 1000 gopher holes ...

Who knows 1000 doesn't include starting and ending ones!

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.

OlgaE · Post by **OlgaE** » Mon Feb 09, 2004 9:01 pm

Please, what's wrong with this code? Can it be precision errors?

[cpp]

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

kiha · Post by **kiha** » Fri Mar 05, 2004 11:40 pm

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]

titid_gede · Post by **titid_gede** » Sat Mar 06, 2004 7:13 pm

could you tell how did you solve this problem? i mean what is your algo? and what for is your 1..10000 array?

kiha · Post by **kiha** » Sat Mar 06, 2004 10:59 pm

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

titid_gede · Post by **titid_gede** » Sun Mar 07, 2004 11:51 am

havent look though your code, but i think your problem is precision error. try to avoid using sqrt

good luck!

kiha · Post by **kiha** » Sun Mar 07, 2004 3:26 pm

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]

OJ Board