日常训练题解

D.Triangle Formation

You are given N wooden sticks. Your task is to determine how many triangles can be made from the given sticks without breaking them. Each stick can be used in at most one triangle.

Input

Output

Example

2
1 1

0

3
2 2 2

1

6
2 2 3 4 5 6

2

 #include<cstring>

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int a[],flag[];

 int main(){

     int n;

     while(~scanf("%d",&n)){

         memset(flag,,sizeof(flag));

         for(int i=;i<n;i++){

             scanf("%d",&a[i]);

             flag[i]=;

         }

         sort(a,a+n);

         if(n<=)printf("0\n");

         else{

             int num=;

             for(int i=;i<n;i++){

                 for(int j=;j<n;j++){

                     for(int k=;k<n;k++){

                         if(i!=j&&i!=k&&j!=k&&flag[i]==&&flag[j]==&&flag[k]==&&a[i]+a[j]>a[k]&&a[i]+a[k]>a[j]&&a[k]+a[j]>a[i]){

                             num++;flag[i]=;flag[j]=;flag[k]=;

                         }

                         else continue;

                     }

                 }

             }

             printf("%d\n",num);

         }

     }

     return ;

 }