Triangle

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

Problem Description
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≤20), which indicates the number of test cases.

For each test case, there is only one line describing the given integer n ( 1≤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
 

Source
2016中国大学生程序设计竞赛（长春）-重现赛



思路：

题意：有长为1,2,,…,n的木棍各一根，现在要拿走尽可能少的木棍使得从剩下的木棍中任取三根均不能构成三角形。
题解：打表，或者观察到结果即为n减去不大于n的 Fibonacci number 的个数。

我一开始的想法是想dfs，然后队友骆骆大神说是暴力打表，每次去掉出现次数最多的边。。%%%%


代码： 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
    int T,n;
    scanf("%d",&T);
    for (int t=1;t<=T;t++) {
        scanf("%d",&n);
        printf("Case #%d: ",t);
        if (n<=3) puts("0");
        else {
            int x=1;
            int y=2;
            int ans=2;
            while (y<=n) {
                int z=x+y;
                x=y;
                y=z;
                ans++;
            }
            ans--;
            printf("%d\n",n-ans);
        }
    }
    return 0;
}