Cod sursa(job #457239)

Utilizator crisvirusDutescu Cristian crisvirus Data 18 mai 2010 17:26:24
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<stdio.h>
int v[801],n;
int cautbin(int a)
{
	int pas=1<<9,i;
	for(i=0;pas;pas=pas/2)
		if (i+pas<=n && v[i+pas]<=a)
			i+=pas;
	return i;
}

int main()
{
	int i,j,aux=0,k,t=0;
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&v[i]);
	for (i=1;i<=n-1;i++)
		for (j=i+1;j<=n;j++)
			if (v[i]>v[j])
			{
				aux=v[i];
				v[i]=v[j];
				v[j]=aux;
			}
	for (i=1;i<=n-1;i++)
		for (j=i+1;j<=n;j++)
		{
			k=cautbin(v[i]+v[j]);
			t+=k-j;
		}
	printf("%d\n",t);
	return 0;
}