## 10398 - The Golden Pentagon

Moderator: Board moderators

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

### 10398 - The Golden Pentagon

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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
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
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
Contact:

### 10398(the golden pentagon)

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
Contact:
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
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### Hehe

Judge solution keeps upto 16 decimal places .

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Contact:
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

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
Contact:

### 10398 why WA

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
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
Contact:
I cannot realize your method.Pls describe your method to solve it with algorithm.

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
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
Contact:
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