CUC-SUMMER-3-I

I - Triangle

HDU - 5914

Mr. Frog has n sticks, whose lengths are 1,2, 3⋯⋯n respectively. Wallice is a bad man, so he does not want Mr. Frog to form a triangle with three of the sticks here. He decides to steal some sticks! Output the minimal number of sticks he should steal so that Mr. Frog cannot form a triangle with
any three of the remaining sticks.

Input
The first line contains only one integer T (T≤20T≤20), which indicates the number of test cases.

For each test case, there is only one line describing the given integer n (1≤n≤201≤n≤20).

Output
For each test case, output one line “Case #x: y”, where x is the case number (starting from 1), y is the minimal number of sticks Wallice should steal.

Sample Input
3
4
5
6
Sample Output
Case #1: 1
Case #2: 1
Case #3: 2

题意：从1到n的序列，去掉一些数，使剩下的数不能构成三角形。

解法：斐波纳挈数列，三角形两边之和不能大于第三边，首先1和2保留，还能剩下的数等于它前两个剩下的数之和

代码：

#include<iostream>
using namespace std;
int fib(int k)
{
    int a=1,b=2;
    int temp,ans=1;
    while(b<=k){
        temp=a;
        a=b;
        b+=temp;
        ans++;
    }
    return k-ans;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        cout<<"Case #"<<i+1<<": "<<fib(k)<<endl;
    }
    return 0;
}