题目链接: https://www.nowcoder.com/acm/contest/135/g
题目描述
从前,Apojacsleam家的水族箱里,养了一群热带鱼。
在这几条热带鱼里,Apojacsleam特别喜欢一条叫做TbGx(请勿人肉)的热带鱼,所以每次都让她第一个吃食物。对于每一条鱼,Apojacsleam都有一个顺序,鱼会按照这个顺序排序,越靠前的地位越高。
吃饱喝足是要睡觉的,这是人的刚需,也是鱼的刚需。
如果TbGx吃了Apojacsleam的食物,她就会睡觉(睡觉时长远小于一天)。这时第二条鱼还是饥肠辘辘的,第二条鱼就可以吃掉TbGx,那么第二条鱼又会睡觉......
注意:Apojacsleam养的鱼比Apojacsleam的智商高到不知道哪里去了,他们都是绝顶聪明的;而他们又是极其守规矩的,即他们不会多鱼分食一条鱼或者食物,只是按照顺序吃;当某一条鱼前面的鱼睡着以后,他可以选择不吃这条鱼,那么别的鱼(还活着的)也不会吃这条,即按照顺序的吃。
一开始,水族箱里只有TbGx一条鱼(未成年),但是,一条鱼成长两天就会成年,成年后就可以繁殖(无性繁殖?别问我我不知道),一天能繁殖一个后代。小鱼也会吃鱼的偶!
请问在前n天中,TbGx最多多少天可以吃饭?
Apojacsleam不希望TbGx饿着,所以你必须在1s内回答。
输入描述:
输入数据有多组,每组一个正整数n,意义如“题目描述”
输出描述:
对于每组输入数据,一行输出: 即前n天中,最多有多少天TbGx可以吃饭。
示例1
说明
第1天,1条鱼,能吃;
第2天,1条鱼,能吃;
第3天,2条鱼,不能吃;
第4天,3条鱼,能吃;
第5天,5条鱼,能吃;
第6天,8条鱼,不能吃;。
思路:从示例说明中看出鱼的数量是一个 斐波那契数列,并且数目为奇数的时候可以吃。所以达打表找规律
代码:
#include "common.h" int main(int argc, char const *argv[])
{
/*//打表找规律
int f[25];
f[1]=f[2]=1;
for(int i=3;i<=20;i++)
f[i]=f[i-1]+f[i-2]; for(int i=1;i<=20;i++){
int cnt=0;
for(int j=1;j<=i;j++)
if(f[j]&1)
cnt++;
debug_b(i),debug_l(cnt);
}
*/ long long n;
while(cin>>n){
if(n%== || n%==){
cout<<(n/+(n+)/)<<endl;
}else{
cout<<(+n/+(n+)/)<<endl;
}
} return ;
}