TOJ 3845.Cut Stick（斐波那契）

题目链接：http://acm.tju.edu.cn/toj/showp3845.html

3845.    Cut Stick

---

Time Limit: 1.0 Seconds    Memory Limit: 65536K Total Runs: 546    Accepted Runs: 259

---

Ann meets another problem.

Since she has a n-meter-long stick, she wants to cut it into small ones. Of course she would not let the small sticks shorter than 1 meter. At the same time she is so mean that she can't stand that any three of the small sticks could spell a triangle. That is to say, any 3 of the small sticks can not form a triangle if there are 3 or more small sticks.

You can simple assume that the small sticks only have integer length.

Input

A line contains a positive integer n, which is the length of the long sticks. It does not exceed 10^5.

Output

Print a number -- the maximum number of small sticks Ann could get.

Sample Input

1 2 3 4

Sample Output

1 2 2 3

Source: TJU 2012 Team Selection

---

Submit   List    Runs   Forum   Statistics

剪棍子，在满足任意三根木棍不能构成三角形的前提下问最多可以剪成几根。众所周知，构成三角形的条件是任意两边的长度要大于第三边的长度，因此为了尽可能多的剪，所以从1开始，每次剪棍子都要满足不大于（也就是等于）前边两次剪得长度和：

#include <stdio.h> using namespace std; int main(){ int l; while(~scanf("%d",&l)){ int a=0,b=1,m; for(m=1;;m++){ l-=b; if(a+b>l) break; int tmp=a; a=b; b+=tmp; } printf("%d\n",m); } }

按此思路写完才发现，这不就是斐波那契数列么，于是悲伤地用斐波那契重写了一遍。。。

#include <stdio.h> int febo[100001]={1,1}; int main(){ for(int i=2;i<100001;i++) febo[i]=febo[i-1]+febo[i-2]; int l,m; while(~scanf("%d",&l)){ m=0; while(l>=febo[m]) l-=febo[m++]; printf("%d\n",m); } }