I found a cool pattern too.
I compute numerator and denominator separately. Kind of DP style, where numerator value for n foldings depends on the numerator value for n-1 foldings.
Two arrays num[] and den[] are used for numerator and denominator.
Set base case num[1], den[1], num[2], den[2] as 1, 2, 1, 4 respectively.(for 1/2, 1/4)
for i = 3 to i = N (here N = 25 max constraint):
den[i] = 2^i
if i is odd: num[i] = 2 * num[i-1] + 1
if i is even: num[i] = 2 * num[i-1] - 1
So we have precomputed till N.
We just need to display num[n] and den[n] for any given value of n (no. of foldings) now.
My Solution: CodeChef: Practical coding for everyone
I posted it in the PRDRG - Editorial topic but I’ll post it here too cuz why not?
The first ridge is at distance \frac12, the second is at \frac{1}{2}-\frac{1}{4}, the third ridge at \frac{1}{2}-\frac{1}{4}+\frac{1}{8}, the fourth ridge is at \frac{1}{2}-\frac{1}{4}+\frac{1}{8}-\frac{1}{16}…
Notice a pattern?
The n^{\text{th}} ridge is at a distance of
I had the same problem when one of my senior told me that I interpreted it wrong. Only the top layer needs to be folded each timethat makes it 1/2 1/4 3/8 and so on.I have done it by adding the fractions.Have attached the link to the code. For any further queries, feel free to ask any question.
Hopefully, you leave enough trees for coming generations.
As for the problem, I sincerely wish you manage to solve this problem during the contest (with or without wife), and if not, I have written Editorial for this problem which may help you.
Lastly, for god, I hope God will find in his heart to accept you back.
