Just another WordPress.com site

Let g(n) denote the number of calls for fib(n)

Then clearly
          g(n) = g(n-1) + g(n-2) + 1

Base cases:
         g(0) = 1
         g(1) = 1

formula:

      dd[m]=(dd[m-1]+dd[m-2]+1)%b;

 

Code:

    #include <cstdio>
#include<iostream>
using namespace std;

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–;
        cout<<m<<endl;
        printf(“Case %ld: %lld %ld %ld\n”,cases,n,b,dd[n%m]);
    }
    return 0;
}

Comments on: "Solution Of ACM UVA 10518-How Many Calls?" (3)

  1. I have a problem in ACM problem 10518 HOW MANY CALLS?it has a wrong answer please help me when i submitted this code in UVA online site in my account it shows wrong answer error please anyone hlp me

  2. Have you submitted this code ?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: