KK's Steel

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 350 Accepted Submission(s): 166

Problem Description

Our lovely KK has a difficult mathematical problem:he has a N(1≤N≤1018) meters steel,he will cut it into steels as many as possible,and he doesn't want any two of them be the same length or any three of them can form a triangle.

Input

The first line of the input file contains an integer T(1≤T≤10), which indicates the number of test cases.

Each test case contains one line including a integer N(1≤N≤1018),indicating the length of the steel.

Output

For each test case, output one line, an integer represent the maxiumum number of steels he can cut it into.

Sample Input

Sample Output

Hint

1+2+3=6 but 1+2=3 They are all different and cannot make a triangle.

要求：给一个长整形数n让你把n分成若干份，1、任意两份长度不能相等 2、任意三分不能组成三角形

分析：因为斐波那契数列中的数满足此要求，所以从这个方面入手，只要分成的数满足a+b<=c即可，所以我们在数列1 2 3 5 8 13 21 ......的数中选取，如果前i项的和等于n输出i如果前i项的和大于n输出i-1

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

#define MAX 100100

#define INF 0x3f3f3f

#define LL long long

using namespace std;

LL fb[10010];

LL f[1001];

void biao()

{

	LL i,j;

	fb[1]=1;

	fb[2]=2;

	for(i=3;i<120;i++)

	    fb[i]=fb[i-1]+fb[i-2];

	f[1]=fb[1];

	for(i=2;i<120;i++)

	    f[i]=f[i-1]+fb[i];

}

int main()

{

	int t,i,j;

	LL n;

	biao();

	scanf("%d",&t);

	while(t--)

	{

		scanf("%lld",&n);

		for(i=1;i<120;i++)

		{

			if(n==f[i])

			{

				printf("%d\n",i);

				break;

			}

			if(n<f[i])

			{

				printf("%d\n",i-1);

				break;

			}

		}

	}

	return 0;

}

巴特西

BestCoder Round #71 (div.2) （hdu 5620 菲波那切数列变形）

KK's Steel

最新文章

热门文章