10566 - Crossed Ladders

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

Moderator: Board moderators

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo » Tue Oct 14, 2003 2:29 pm

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.
Last edited by yahoo on Tue Oct 14, 2003 8:47 pm, edited 1 time in total.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Tue Oct 14, 2003 2:46 pm

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.

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo » Tue Oct 14, 2003 8:42 pm

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. :wink: :wink: :wink:

davor
New poster
Posts: 8
Joined: Sat Jun 28, 2003 11:04 pm

10566 - Crossed ladders

Post by davor » Fri Oct 31, 2003 8:07 pm

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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Sat Nov 01, 2003 12:41 am

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

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Sat Nov 01, 2003 12:42 am

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

zubair
New poster
Posts: 17
Joined: Fri Apr 18, 2003 2:22 pm

Post by zubair » Sat Nov 01, 2003 11:53 am

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]
Last edited by zubair on Sat Nov 01, 2003 3:11 pm, edited 1 time in total.
zubair-CUET old sailor

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Sat Nov 01, 2003 12:53 pm

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
New poster
Posts: 8
Joined: Sat Jun 28, 2003 11:04 pm

Post by davor » Sat Nov 01, 2003 1:55 pm

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

amd-RS
New poster
Posts: 27
Joined: Thu Sep 05, 2002 7:37 am

10566 - TLE

Post by amd-RS » Tue Nov 04, 2003 6:26 pm

Hello, can you help me with my code ? I

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Tue Nov 04, 2003 9:57 pm

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

amd-RS
New poster
Posts: 27
Joined: Thu Sep 05, 2002 7:37 am

10566 - TLE

Post by amd-RS » Wed Nov 05, 2003 10:54 pm

Hi !!!

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

The root is inside this limits.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Thu Nov 06, 2003 1:07 am

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
New poster
Posts: 27
Joined: Thu Sep 05, 2002 7:37 am

10566

Post by amd-RS » Thu Nov 06, 2003 4:37 pm

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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Thu Nov 06, 2003 6:23 pm

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

10 5 0
5 10 0

Post Reply

Return to “Volume 105 (10500-10599)”