ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1462. Uncle Scrooge's Gold

How to make it fast? Is my formula correct?
Posted by Alexey 23 Aug 2006 19:59
I use Fib(n-1)+Fib(n+1).
I can find Fib(n) in O(log n).
But the long arithmetics makes my programm too slow.
Help, please.
Re: How to make it fast? Is my formula correct?
Posted by Cybernetics Team 30 Aug 2006 16:52
Read below some solutions. Your formula is correct, I used it too and recursevly computed the F[n]. I used long arithmetics in base 1.000.000 and it runs quick enough.
Re: How to make it fast? Is my formula correct?
Posted by Denis Koshman 12 Aug 2008 05:33
Better use long arithmetics base 2^P, and then fetch decimal answer by sequential divisions by 1'000'000 or something like that.