Problem B
猴子吃桃 II
问题
现有 n 个桃子,无限可列个小猴子去领桃子吃。在桃子足够的情况下,排
在第 i 位的小猴子领 F (i) 个桃子,这里 F 是 Fibonacci 数列。若轮到第 i 个小
猴子时,剩余的桃子不到 F (i) 个,它就获得所有剩余的桃子,第 i + 1 个及以后
的小猴子就要挨饿了。
万神希望某只小猴子能拿到最多的桃子,那么这只猴子应该排在第几个位
置,又能吃到几个桃子呢?
Fibonacci 数列的定义见 http://oeis.org/A000045 。
输入格式
输入包含多组数据(最多 100 组),请处理到文件结束。
每组数据只有 1 行,包含正整数 n,表示桃子的总个数。
保证 1 ≤ n ≤ 10 18 。
输出格式
对于每组数据输出 1 行,包含两个整数,用空格分割。第一个整数表示小猴
子应该排在第几个位置,第二个整数表示小猴子能吃到几个桃子。
若排在两个位置能吃到的桃子数相同,则输出靠前的位置。
输入样例
1
20
输出样例
1 1
6 8
HINT
请正确使用 64 位整数,详见选手须知。
也没啥说的
/*************************************************************************
> File Name: b.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年04月20日 星期三 12时02分19秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 100;
LL sum[N];
void init()
{
sum[0] = 0;
sum[1] = 1;
sum[2] = 1;
for(int i = 3; i < N; i++)
{
sum[i] = sum[i-1] + sum[i-2];
}
}
int main()
{
init();
LL n;
while(~scanf("%lld", &n))
{
if(n == 3 || n == 2 || n == 1)
{
printf("1 1\n");
continue;
}
LL t = n, left, ans, left_pre;
for(int i = 1; i < N; i++)
{
if(t > sum[i])
{
t-=sum[i];
continue;
}
else{
left = t;
left_pre = sum[i-1];
ans = i;
break;
}
}
if(left > left_pre)
{
printf("%lld %lld\n", ans, left);
}
else{
printf("%lld %lld\n", ans - 1, left_pre);
}
}
return 0;
}