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