10518 - How Many Calls?
Moderator: Board moderators
-
- 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!
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!
Try the following case:
If you're not careful, then you'd say "-1"
![:D](./images/smilies/icon_biggrin.gif)
Code: Select all
22799 308
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
10518 WA ?
why wa ?
[c] Now, I get AC[/c]
Thank you, Lars Hellsten
[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.
-
- New poster
- Posts: 20
- Joined: Thu Apr 10, 2003 10:53 pm
Re: 10518 WA ?
I think the second %i should be %lli.pingus wrote:why wa ?
[c]
printf("Case %i: %i %i %i\n",cases,n,b,calls[n%(m-1)]);
[/c]
-
- 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-
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).
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
I would be really happy
thanx in advance
PS: if someone could explain pingus' algo, that would be another great thing...
Code: Select all
( x^n / m ) mod z
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.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
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.
-
- New poster
- Posts: 20
- Joined: Thu Apr 10, 2003 10:53 pm
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.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...
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).
-
- Learning poster
- Posts: 82
- Joined: Thu Oct 10, 2002 1:15 pm
- Location: St. Johns, Canada
- Contact:
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
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]
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]