Cod sursa(job #373755)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 14 decembrie 2009 23:14:38
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<cstdio>
#include <algorithm>
#define max 1000
using namespace std;
int x,m,nr=0,n,k,v[max+1];
int main()
{int i,j;
        freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
        scanf("%d",&x);
        for(i=1;i<=x;i++)
            scanf("%d",&v[i]);
	sort(v+1,v+x+1);
	for(i=1;i<=x-2;++i)   
	{   
	k=i+2;   
	for(j=i+1;j<=x-1;++j)   
	{   
	     while(k<=x && v[i]+v[j]>=v[k])   
	           ++k;   
	     nr+=k-j-1;//k=indicele primului care nu e bun=>toate cele dintre j+1 si k-1 sunt bune   
         
       	}   
	}   
       printf("%d\n",nr);   


 return 0;

}