2016西电校赛网络赛Problem B 猴子吃桃 II

2019-04-13 21:04发布

站内文章 / 模拟电子
11464 0 1429

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 #include #include #include #include #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 "); 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 ", ans, left); } else{ printf("%lld %lld ", ans - 1, left_pre); } } return 0; }