Cod sursa(job #769807)

Utilizator MtkMarianHagrSnaf MtkMarian Data 20 iulie 2012 21:31:59
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<cstdio>
#include <algorithm>
using namespace std;
int *l,rez;

int cauta(int c, int b, int n) {
   
	int m;
	
    while (b < n)
	{
        m = (b + n) / 2;
        if (l[m] <= c)
            b= m + 1;
        else
            n = m;
    }

    m = (b + n) / 2;
    if (l[m] >c)
       -- m;
    return m;
}

int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	int n,sum=0;
	scanf("%d",&n);
	

	l=new int[n+2];

	for(int i=1;i<=n;i++)
	{
	scanf("%d",&l[i]);
	
	}
	sort(l+1,l+n+1);

	
	


	for(int i=1;i<n;i++)	
		for(int j=i+1;j<=n;j++)
		{
		rez=cauta(l[i]+l[j],j+1,n);
		
		if(rez!=i&&rez!=j)
		{
			//printf("%d scrie i %d scrie j %d\n",rez,i,j);
			sum+=rez-j;
		}
		}
		printf("%d\n",sum);

	

	return 0;

}