Cod sursa(job #406920)

Utilizator HoriaClementHoriaC HoriaClement Data 1 martie 2010 21:36:26
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<stdio.h>
#include<algorithm>

using namespace std;
int n;
long v[1010];

void read()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%ld",&v[i]);
	v[++n]=999999999;
}
int cautare(long x,long poz)
{
	int st=poz,dr=n,m;
	if(v[poz]>=x)
		return poz;
	while(st!=dr)
	{
		m=(st+dr)>>1;
		if(x<=v[m])
		dr=m;
		else
			st=m+1;
	}
	return st;
}

void rez()
{
	int i,j;
	long s=0;
	for(i=1;i<=n-3;i++)
	for(j=i+1;j<=n-2;j++)
	s=s+(cautare(v[i]+v[j]+1,j+1)-1-j);
	printf("%ld\n",s);
}

int main()
{
	read();
	sort(v+1,v+n+1);
	rez();
	return 0;
}