F 三角形
链接:https://ac.nowcoder.com/acm/contest/5758/F
来源:牛客网
题目描述
小明有一根长度为a的木棒,现在小明想将木棒分为多段(每段木棒长度必须为整数),
使得分隔后的木棍中,取出的任意三段都不能构成三角形,小明想知道木棒最多被分成几段?
输入描述:
输入数据的第一行是t,表示数据的组数, 接下来每组数据输入一个a
(t<=1000, 1 <= a < 2^64 - 1)
输出描述:
对于每组输入样例,打印木棒最多被分为多少段
输入
2 1 3
输出
1 2
我的代码
#include<stdio.h>
int main()
{
int t,flag=1;
scanf("%d",&t);
unsigned long long int dp[50000];
unsigned long long int sum[50000];
unsigned long long int k=18446744073709551615ull;
dp[1]=1ull;
sum[1]=1;
dp[2]=1ull;
sum[2]=sum[1]+dp[2];
for (int i=3;i<92;i++)
{
dp[i]=dp[i-1]+dp[i-2];
sum[i]=sum[i-1]+dp[i];
//printf("%llu\n",dp[i]) ;
//printf("%llu\n",sum[i]) ;
}
while(t--)
{
long long int a;
scanf("%llu",&a);
int l=1,r=91,mid;
while(l<=r)
{
mid=(l+r)/2;
if (sum[mid]>a)
{
r=mid-1;
mid=(l+r)/2;
}
else
{
l=mid+1;
mid=(l+r)/2;
}
}
printf("%d\n",mid);
}
return 0;
}