Cod sursa(job #350845)

Utilizator pirvupirvu tudor pirvu Data 26 septembrie 2009 09:57:37
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<cstdio>

long i,j,n,numar;

int ok;

long a[1<<10];


int cautare(long x)
{
	long i,pas;
	for (pas=1;pas<=n;pas<<=1);
	for (i=0; pas; pas>>=1)
		if (i+pas<=n &&  a[i+pas]<=x)
			i+=pas;
	if (i==0) return n;
	return i;
}



void schimba(long k)
{
long aux=a[k];
a[k]=a[k+1];
a[k+1]=aux;
	
}

int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%ld", &n);
	
	for (i=1;i<=n;i++)
	scanf("%ld", &a[i]);
	
	do
	{
		ok=1;
		for (i=1;i<n;i++)
			if (a[i]>a[i+1])
			{
				schimba (i);
				ok=0;
			}
	}while (ok==0);
	
	long nn=n-1;
	for (i=1;i<nn;i++)
		for (j=i+1;j<n;j++)
		{
			long c2=cautare(a[i]+a[j]);
			numar+=c2-j;
		}
	printf("%ld", numar);
	
	return 0;
	
}