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

@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