XidianOJ 1139 猴子吃桃Ⅱ

--正文

预处理即可

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

long long n;
long long f[101],sum[101];


int main(){
    f[0] = 0; f[1] = 1;
    sum[1] = 1;
    int i;
    for (i=2;i<=100;i++){
        f[i] = f[i-1] + f[i-2];
        sum[i] = sum[i-1] + f[i];
    }
    while (scanf("%lld",&n) != EOF) {
        if (n == 3) {
            printf("1 1
"); 
            continue;
        }
        int x = lower_bound(sum,sum+100,n) - sum;
        long long y = n - sum[x-1];
        if (y > f[x-1]) printf("%d %lld
",x,y);
        else printf("%d %lld
",x-1,f[x-1]);        
    }
    
    return 0;
}