ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1462. Uncle Scrooge's Gold

WHY WA at test 4
Posted by SPIRiT 19 Sep 2006 19:02
I use this formula: f(N)+f(n-2) where F(0)=1, F(1)=1, F(N)=F(N-1)+F(N-2). But wa. What is in the test 4. I checked the answer for N=7000 at the forum and it matches the answer that my program gives. Can anybody give me a test for 4.
This problem does not need log(N) methods
Posted by SPIRiT 25 Sep 2006 12:39
We can state that f(21)=4181*f(1)+6765*f(2), f(22)=6765*f(1)+10946*f(2). Wherefore we can calculate f(i),f(i+1) with N/20 operations. All we need is addition of two long numbers (I used base 10000 for them) and  multiplication of long number and simple one, that's all. The usage of recursion formula f(2n)=f^2(n)+f^(n+1) (or something like that) is overridden here by the cost of multiplication of two long numbers.
Re: This problem does not need log(N) methods
Posted by Todor Tsonkov 25 Sep 2006 14:07
@Spirit:
If you want to I can give you my accepted Java source, please give me your mail, but I'm interested in any accepted C++ solutions, please send to tabledott@gmail.com, cause all my C++ efforts were unsucessful, btw I used base 10^9 and I was    losing accuracy :)
Re: This problem does not need log(N) methods
Posted by Olly 25 Feb 2007 17:04
I'll send you my C++ solution.
I made it in O(n) with only + in long arithmetics, but it's well optimized.

If anybode else is interested in my solution mail to me alutsenko[at]bk[dot]ru