HDU 5620 KK's Steel (斐波那契序列)

时间:2023-02-03 18:12:56

KK's Steel

题目链接:

http://acm.hust.edu.cn/vjudge/contest/121332#problem/J

Description

Our lovely KK has a difficult mathematical problem:he has a 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 , which indicates the number of test cases.

Each test case contains one line including a integer ,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

1

6

Sample Output

3

Hint

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

题意:

把数字N分成尽量多个互不相同的数字;

要求任意两个互不相同;

任意三个不能组成三角形;

题解:

举几个例子推导一下很容易得出规律:

斐波那契序列.

判断N最多能由分成多少个不同的斐波那契数之和即可.

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define LL long long
#define eps 1e-8
#define maxn 3300
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std; LL n; int main(int argc, char const *argv[])
{
//IN; int t; cin >> t;
while(t--)
{
scanf("%I64d", &n);
if(n==1 || n==2) {printf("1\n");continue;}
int cnt = 2;
LL first = 1;
LL second = 2;
n -= 3;
while(1) {
if(n <=0) break;
LL tmp = second;
second = first + second;
first = tmp;
n -= second;
cnt++;
} if(n!=0) cnt--;
printf("%d\n", cnt);
} return 0;
}