OJ Board

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

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

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]

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

thanks, I got AC.

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. Could someone tell me what's wrong with my code.
Thx

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

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

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.

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]

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]

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

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

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

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]