首页 > ACM题库 > HDU-杭电 > HDU 3054-Fibonacci[解题报告]HOJ
2014
02-27

HDU 3054-Fibonacci[解题报告]HOJ

Fibonacci

问题描述 :

We know the Fibonacci Sequence

F1=1,F2=1,F3=2,F4=3,F5=5,

Fx = Fx-1+Fx-2

We want to know the Mth number which has K consecutive "0" at the end of Fx.

For example,

F15=610

It is the first number which has only one "0" at the end.

F300=222232244629420445529739893461909967206666939096499764990979600.

It is the second number which has two "0" at the end.

Of course, the Fx may be very large if M and K are big. So we only want to know the subscript of Fx (it means the "x" For a given M and K)

输入:

Input includes multiple cases.

First line is the number of case x

The next x lines: Each line contains two integer number, K and M, divided by a space.

输出:

Input includes multiple cases.

First line is the number of case x

The next x lines: Each line contains two integer number, K and M, divided by a space.

样例输入:

3
1 1
2 2
2 5 

样例输出:

15
300
900 

#include<stdio.h>
#include<math.h>

int fac[22]={0,1,1};
double f=(sqrt(5.0)+1.0)/2.0;
int main()
{
    double bit;
    int n;
    for(int i=3;i<=20;i++)  fac[i]=fac[i-1]+fac[i-2];
    while(scanf("%d",&n)!=EOF)
    {
        if(n<=20)
        {
            printf("%d\n",fac[n]);
            continue;
        }
        bit=-0.5*log(5.0)/log(10.0)+((double)n)*log(f)/log(10.0);
        bit=bit-floor(bit);
        bit=pow(10.0,bit);
        while(bit<1000)
        {
            bit=bit*10.0;
        }
        printf("%d\n",(int)bit);
    }
    return 0;
}

  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }