科林明伦杯

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;
}

发表评论