OJ Board

I havent been able to find the explicit formula for 10518, perhaps someone can give me a hint?

I found the recurrence:
F[n] = F[n-1] + F[n-2] + 1

but have no idea how to convert it to a formula or a Q-matrix type... thanks!

Original Fib the Question we want
f(0)=1 f'(0)=1
f(1)=1 f'(1)=1
f(2)=2 f'(2)=3
f(3)=3 f'(3)=5
f(4)=5 f'(4)=9
f(5)=8 f'(5)=15
f(6)=13 f'(6)=25
f(7)=21 f'(7)=41
f(8)=34 f'(8)=67
f(9)=55 f'(9)=109
f(10)=89 f'(10)=177
We can see f'(n)=f'(n-1)+f'(n-2)+1 and f'(n)=2*f(n)-1

Can anyone who got AC post some test data?
Thanks.

Ah, didn't realize this, thanks!

Try the following case: If you're not careful, then you'd say "-1"

why wa ?

[c] Now, I get AC[/c]

Thank you, Lars Hellsten

pingus wrote:why wa ?
[c]
printf("Case %i: %i %i %i\n",cases,n,b,calls[n%(m-1)]);
[/c]

I think the second %i should be %lli.

Two things I noticed ...

1. If base = 1, there's no way you can get a 1 back on your subsequent calculations (unless m wraps-around) ... Wouldn't you get a TLE instead ???

2. I tried on approach like yours on scanf("%llu", ...) ... it didn't work for me for large numbers ... so I changed it to scanf as string and calculate the long long myself.

-turuthok-

i got stuck on this problem - I was trying to use the explicit formula for the nth fibonacci numbers, and then multiply by two, minus one, but above a certain range I get infinity fro the nth fibonacci number - not surprisingly it doesn't fit into a long double... so if someone could explain me the expansion/simplification rules for I would be really happy
thanx in advance
PS: if someone could explain pingus' algo, that would be another great thing...

Note that given a 2-vector [fib(n-1), fib(n)]^T, there is a 2x2 matrix that turns it into [fib(n), fib(n+1)]^T, namely [0 1; 1 1]. Recall something from linear algebra about compositions of linear transformations, apply a minimal amount of intelligence, and you can do this problem in O(log(n)) time. The closed form is too messy for this problem, and long doubles make it much, much messier with roundoff error and the like.

ya, you can do Lucas number the same way, I believe, I don't know how other ppl do it though, because mine runs pretty fast and there are some really slow solution for some reason...

Larry wrote:ya, you can do Lucas number the same way, I believe, I don't know how other ppl do it though, because mine runs pretty fast and there are some really slow solution for some reason...

Those people used a different method, where you compute values in the sequence until the sequence begins to repeat itself after k terms, then the answer is the (n%k)-th term. k can get as large as 10,000 or so. I did it this way since I didn't see the f(n) = 2*fib(n) - 1 relationship immediately.

If you implement the iteration method by storing an array of all the values generated, that's pretty slow, and probably the cause of the times > 0.5s. If you simply use two int variables and stop when they both equal 1, then the compiler can do everything in registers with no memory accesses at all, which makes it quite fast (I got 0.040s).

This page hel me a great to think about how i can solve this problem
but i am geting WA. Here is my code.
Can any one tell me why i am getting WA.
[cpp]
#include <iostream.h>

main()
{

int calls[1000000];
int cases, b, m;
long long int n;

cases = 0;
while(1)
{
cases++;
// scanf("%llu %i",&n,&b);
cin >> n >> b;
// cout << n << " " << b << endl;
if ((n == 0)&&(b == 0)) break;

calls[0] = 1;
calls[1] = 1;
calls[2] = (3 % b);
m = 2;

while (1)
{
if ((calls[m] == 1)&& (calls[m-1] == 1)) break;
m++;
calls[m] = (1 + calls[m-1]+ calls[m-2]) % b;
}

// printf("Case %i: %i %i %i\n",cases,n,b,calls[n%(m-1)]);
cout <<"Case "<< cases <<": "<<n<<" "<<b<<" "<<(calls[n%(m-1)])%10<< endl;
}
return 0;
} [/cpp]

Thanks in advance

M H Rasel
CUET Old Sailor

it's not need to add "%10"

one of my ac programs:
[cpp]

#include <stdio.h>
long dd[1000000];
int main()
{
long long n;
long b,m;
long cases=0;


while(1){
scanf("%lld%ld",&n,&b);
if(!n && !b) break;
cases++;

dd[0]=1;
dd[1]=1;
for(m=2;m<1000000;m++){
dd[m]=(dd[m-1]+dd[m-2]+1)%b;
if(dd[m]==1 && dd[m-1]==1) break;
}
m--;
printf("Case %ld: %lld %ld %ld\n",cases,n,b,dd[n%m]);
}
return 0;
}
[/cpp]

I need some i/o.

Suman.