10566 - Crossed Ladders

[yahoo]

I can't understand why i got wrong answer. i have used binary search. Can anybody help me with some test cases.
Here is my code:

Code: Select all

cutted. But after some modification it got accepted. thanks to all.

[Yarin]

Instead of breaking when fabs(d)<1e-7, break when the difference between l and h is sufficiently small (say 1e-6) since it's this value you should output.

As it is now, you could probably get WA when x,y,c are high numbers and thus z becomes quite small.

[yahoo]

Thank you very very much yarin for your kind reply. Finally i got accepted. It seems that i had to think a lot about this kind of mistakes. Thanks again.

[davor]

Can anyone find what's wrong with my solution? If h1 and h2 are heights of ladders on walls then sqr(d)=sqr(x)-sqr(h1) , sqr(d)=sqr(y)-sqr(h2) , and h/h2=(h1-h)/h1. From this we have equation (sqr(x)-sqr(h1)-sqr(y))*sqr(h-h1)+sqr(h*h1)=0. Now I'm finding h1 with binary search, and then d. What's wrong. Here's my code:
[pascal]
var l1,l2,h,v1,v2:double;

function test(h1:double):double;
var e,f,g:double;
begin
e:=sqr(h1-h); f:=sqr(l1)-sqr(h1)-sqr(l2);
test:=e*f+sqr(h)*sqr(h1);
end;

begin
while not eof(input) do begin
readln(l1,l2,h);
if l1<l2 then
begin
v1:=l1;
l1:=l2;
l2:=v1;
end;
v1:=0; v2:=l1;
while (v2-v1)>0.0001 do begin
if test((v2+v1)/2)<0 then v2:=(v2+v1)/2 else v1:=(v2+v1)/2;
end;
writeln(sqrt(l1*l1-v2*v2):0:3);
end;
end.
[/pascal]

[Maarten]

Your answer is not accurate enough. Change the constant 0.0001 to 0.000001 and you will get accepted right away

[Maarten]

Your answer is not accurate enough. Change the constant 0.0001 to 0.000001 and you will get accepted right away

[zubair]

hi,
i run bisection for this problem but i don't know why i am getting w/a.
can any body help?
[cpp]
arios
[/cpp]

[Maarten]

i am not sure but i think it is an accuracy problem as well. I think you should change the code
[cpp]if(fabs(eqn)<0.0000001)

{
printf("%.3lf\n",mid);
break;

}
[/cpp]

into something like

[cpp]if( fabs(temp1-temp)<0.0000001) { ... }[/cpp]
since temp is basically the value you want to output.

I hope this helps; as I said I'm not entirely sure that this is the problem.

[/cpp]

[davor]

Thanks a lot. I got Accepted now. I have to watch on accuracy

[amd-RS]

Hello, can you help me with my code ? I

[Maarten]

what's the purpose of your variables fa and fb ?

[amd-RS]

Hi !!!

fa and fb stores the value of the function, applied to the limits a and b ...

The root is inside this limits.

[Maarten]

what i meant to say is: You calculate fa and fb in your loop but you never use them anywhere in the program. So then why do you calculate them?

[amd-RS]

Maarten, you're right.

I removed that lines, and change fabs(ft) by fabs(a - b) > 1e-15 and now I get Wrong Answer ...

Here some sample input/output for my program ...

Input:

30 40 10
12.619429 8.163332 3
10 10 3
10 10 1
300 400 100
126.19429 81.63332 30
100 100 30
100 100 10
3000 4000 1000
1261.9429 816.3332 300
1000 1000 300
1000 1000 100
30000 40000 10000
12619.429 8163.332 3000
10000 10000 3000
10000 10000 1000

Output:

26.033
7.000
8.000
9.798
260.329
70.000
80.000
97.980
2603.288
700.000
800.000
979.796
26032.878
6999.999
8000.000
9797.959

[Maarten]

my program gives the same answers as yours. But how about these:

10 5 0
5 10 0