Cod sursa(job #1018)

Utilizator DorinOltean Dorin Dorin Data 12 decembrie 2006 14:04:36
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
# include <stdio.h>

# define input "nrtri.in"
# define output "nrtri.out"

# define max 804

long a[max],n,i,rez,j,k,aux,ok,val,m;

long cauta(long x,long st,long dr)
{
	while(st <= dr)
	{
		m = (st+dr)/2;
		if(a[m] <= x && a[m+1] > x)
			return m;
		if(a[m]<=x)
			st = m+1;
		else
			dr = m-1;
	}
	return 1;
}

int main()
{
	freopen(input,"r",stdin);
	freopen(output,"w",stdout) ;

	scanf("%ld",&n);

	for(i = 1;i<=n;i++)
		scanf("%ld",&a[i]);

	do
	{
		ok = 1;
		for(i = 1;i<=n-1;i++)
			if(a[i] > a[i+1])
			{
				aux = a[i];
				a[i] = a[i+1];
				a[i+1] = aux;
				ok = 0;
			}
	}while(!ok);

	a[n+1] = 600001;

	for(i = 1;i<=n-2;++i)
		for(j = i+1;j<=n-1;++j)
		{
			val = cauta(a[i] + a[j],j+1,n);
			if(val > j)
				rez+=val-j;
		}

	printf("%ld",rez);

	return 0;
}