10518 - How Many Calls?

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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?

Post by Larry » Sun Jun 22, 2003 10:45 pm

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

Post by windows2k » Mon Jun 23, 2003 1:53 am

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

Post by yatsen » Mon Jun 23, 2003 8:21 am

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:

Post by Larry » Tue Jun 24, 2003 12:47 pm

Ah, didn't realize this, thanks!

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Tue Jun 24, 2003 1:34 pm

Try the following case: :D

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 ?

Post by pingus » Wed Jun 25, 2003 6:22 pm

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 ?

Post by Lars Hellsten » Wed Jun 25, 2003 7:09 pm

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:

Post by turuthok » Thu Jun 26, 2003 1:37 am

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 ?

Post by zsepi » Thu Jun 26, 2003 2:14 am

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
thanx in advance
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

Post by _evilgeek » Thu Jun 26, 2003 5:38 am

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:

Post by Larry » Sat Jun 28, 2003 8:39 am

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

Post by Lars Hellsten » Tue Jul 01, 2003 5:03 am

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
Location: St. Johns, Canada
Contact:

Post by Master » Fri Aug 29, 2003 12:55 pm

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

inkfish
New poster
Posts: 7
Joined: Wed Jul 30, 2003 9:04 am

Post by inkfish » Mon Oct 13, 2003 7:57 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:

Post by sumankar » Wed Mar 30, 2005 10:31 am

I need some i/o.

Suman.

Post Reply

Return to “Volume 105 (10500-10599)”