10398 - The Golden Pentagon

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

Moderator: Board moderators

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

10398 - The Golden Pentagon

Post by Mahbub »

1. I did a binary search to find out r..is it ok?
2. If bin search is ok, to what precesion should i compute

I think this prob needs a special judge..

my r was:

1.3247179572447


3. Is there any other tricky points?

I also handled case with S= 0 specially..

Thanks
Light

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

Post by Adrian Kuegel »

I used binsearch, too and a precision of 1e-15.
If you don't have to print the number of digits, I didn't used pow(10,digits) for calculation, I used s*pow(r,i-1).
And I used an epsilon of 1e-12 for calculation.

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

Post by Mahbub »

Thanks to Adrian. But i was actually getting WA for a silly stupid mistake.
Thanks. I got acc now

Light.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster »

I just tried my luck on this one, too. After getting WA multiple times I finally found out a rounding error in the 15th fractional digit of my value for r (should be 6,not 5). The main problem is (as always in floating point problems) precision.

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Location: Dhaka, Bangladesh
Contact:

10398(the golden pentagon)

Post by Shahid »

i have solved this problem, but got WA....
i used the formula that, the one side of the first and 5th triangle is equal to the 6th trialngle....(i.e. if the one side of the first trianlge is 'S')then the equation becomes S + (S * (r^4)) = S* (r^5)....(here r is the geometrical progression ratio)

by solving we get....(r^4)*(r - 1) = 1......i solved this with 6 places precision after the point. in bisection method by the following code:


[cpp]
long double equation(long double q)
{
return ((q*q*q*q)*(q-1));
}

long double findr(long double lower, long double upper)
{
long double middle, ans;

for(;;)
{
middle = (upper + lower) /2;

ans = fabs(equation(middle) - 1);

if(ans <= E) // E = 0.000001
return middle;

if(equation(middle) < 1.0)
lower = (upper + lower) / 2;
else
upper = (upper + lower) / 2;
}
}
[/cpp]


i initialize the upper and lower variable to 1.5 and 1.

then i use the folowing formula to find out a digit of say, a number N;

digit = ceill(log10(N));

when i printing the number(if digit < 10) i use floor to print the samller round integer number.

so can anyone help me to find out my error?

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan »

Your WA is probably caused by the low precision you're using. My team member Adil got several WA just because he was keeping 14 places after the decimal point!! He finally got AC after keeping 15 places. You might try decreasing the error.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Hehe

Post by shahriar_manzoor »

Judge solution keeps upto 16 decimal places :-) .

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Location: Dhaka, Bangladesh
Contact:

Post by Shahid »

right you are!!!!! the precision is the main factor of this problem............
thanx to both of u.... :)

Cucu
New poster
Posts: 4
Joined: Wed Nov 20, 2002 9:43 pm

I get always WA and there's something I don't understand

Post by Cucu »

HI!
I'm calculating K^(i-1) where K=1,324717...
I've tried with 15 to 20 digits and it doesn't work :(
Also, I've realized that if the first side is 1, the second is 1,32... and the third is 1.7424, and it says "T indicates the length of a side of I-th triangle rounded to the nearest integer", so it should be 2, however if you read the sample output, is written 1. Where's the problem or the thing I'm not understanding?
I've tried booth rounding and flooring, but none works, I've tried also long double and making my own power function, but it doesn't work.
I think my program works, but I got WA always!!! Help please!!
Thanks
Alejandro

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

10398 why WA

Post by erfan »

In this problem i found r=1.32471795724474603;
i also handle specialy for 0 but still WA.
Can any one help me by some sample input output.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

Instead of using that value for r, use Newton's Method to generate the value in your program and use that value.

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

Post by erfan »

I cannot realize your method.Pls describe your method to solve it with algorithm. :lol:

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil »

hello erfan.

your value of r is almost the same as mine. did you consider this line:
If T is not less than 1000000000 then you should output D instead of T, where D is the no of
digit in T.
best of luck.

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

Post by erfan »

Yah, I done it.Again i find no of digit as following way:

digit=log10(r);
digit=digit*(t-1);
digit+=1;
Then floor(digit) and print.

I also cheek
if(digit<10.0) then print T
else digit.
Is there anything miss i. If not pls give me some critical input output.

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

Post by erfan »

Ohho i found my mistake that was to find number of digit.
Now i found AC hi hihihih ki moja... :lol: :lol:

Post Reply

Return to “Volume 103 (10300-10399)”