10610 - Gopher and Hawks

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Kuba12
New poster
Posts: 9
Joined: Sat Jan 11, 2003 1:51 pm

10610 - Gopher and Hawks

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: 10610 - Gopher & Hawks

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

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]

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Shortest path

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
New poster
Posts: 9
Joined: Sat Jan 11, 2003 1:51 pm

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

thanks, I got AC.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: Shortest path

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 :)
Last edited by windows2k on Wed Jan 28, 2004 3:44 pm, edited 1 time in total.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

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
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

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

Bad problem statement!!! :x

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. :)
Retired from SJTU Accelerator 2004

OlgaE
New poster
Posts: 2
Joined: Sat Feb 07, 2004 4:45 pm

10610 - Gopher and Hawks

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
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

10610 Gopher and Hawks WA

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

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

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?
Kalo mau kaya, buat apa sekolah?

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

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 :)
kiha

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

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!
Kalo mau kaya, buat apa sekolah?

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

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

Post Reply

Return to “Volume 106 (10600-10699)”