Cod sursa(job #209342)

Utilizator mihai0110Bivol Mihai mihai0110 Data 21 septembrie 2008 21:03:55
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<stdio.h>
#define MAX 801
int i,j,n,x,aux,poz,rez;
int a[MAX];
int caut(int pi,int x)
{
	int li=pi,ls=n,mij,poz=-1;
	while(li<=ls)
	{
		mij=li+(ls-li)/2;
		if(a[mij]<=x)
		{
			poz=mij;
			li=mij+1;
		}
		else
			ls=mij-1;
	}
	return poz;
}
int main(void)
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
			if(a[i]>a[j])
			{
				aux=a[i];
				a[i]=a[j];
				a[j]=aux;
			}
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
		{
			poz=caut(j+1,a[i]+a[j]);
			if(poz!=-1)
				rez+=(poz-j);
		}
	printf("%d",rez);
	return 0;
}