Triangle

深碍√TFBOYSˉ_ 2022-06-10 13:27 138阅读 0赞

# Triangle #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 1365    Accepted Submission(s): 809**

Problem Description

Mr. Frog has n sticks, whose lengths are 1,2, 3  ⋯![Image 1][]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![Image 1][]), which indicates the number of test cases.  
  
For each test case, there is only one line describing the given integer n (  1≤n≤20![Image 1][]).

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
      
       
      
       
    
      
       
      
       
        
       题意：3个测试样例，每个测试样例有一个数n：表示n根长度分别为1，2,3,........,n的木棍,求最少拿走几根木棍，可以使得剩下的木棍都不能组成三角
      
       
      
       
        
       形
      
       
      
       
    
      
       
      
       
       
        #include <cstdio>
    #include <queue>
    #include <algorithm>
    using namespace std;
    int main()
    {
        int a[25];
        a[1]=a[2]=a[3]=0;
        int n,t;
        queue<int> Q;
        Q.push(3);
        Q.push(2);
        int k=4,ans=0;
        while(k<=20)
        {
            int x=Q.front();
            Q.pop();
            int y=Q.front();
            if(x+y>k)
            {
                ans++;
                a[k]=ans;
                Q.push(x);
            }
            else
            {
                a[k]=ans;
                Q.push(k);
            }
            k++;
        }
        int Cas=1;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            printf("Case #%d: %d\n",Cas++,a[n]);
        }
        return 0;
    }

[Image 1]: