## 10518 - How Many Calls?

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

### 10518 - How Many Calls?

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!

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
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

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan
Can anyone who got AC post some test data?
Thanks.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Ah, didn't realize this, thanks!

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
Try the following case:

Code: Select all

``22799 308 ``
If you're not careful, then you'd say "-1"

pingus
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 pm

### 10518 WA ?

why wa ?

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

Thank you, Lars Hellsten
Last edited by pingus on Wed Aug 13, 2003 4:15 pm, edited 2 times in total.

Lars Hellsten
New poster
Posts: 20
Joined: Thu Apr 10, 2003 10:53 pm

### Re: 10518 WA ?

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.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

### Re: 10518 WA ?

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

Code: Select all

``( x^n / m ) mod z``
I would be really happy
PS: if someone could explain pingus' algo, that would be another great thing...
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

_evilgeek
New poster
Posts: 2
Joined: Thu Jun 19, 2003 4:32 am

### Matrices

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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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...

Lars Hellsten
New poster
Posts: 20
Joined: Thu Apr 10, 2003 10:53 pm
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).

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Contact:
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]

M H Rasel
CUET Old Sailor

inkfish
New poster
Posts: 7
Joined: Wed Jul 30, 2003 9:04 am
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]

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
I need some i/o.

Suman.