Cod sursa(job #285443)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 22 martie 2009 16:40:37
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<stdio.h>
int n;
long v[1010];

void read()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++)
		scanf("%ld",&v[i]);
	v[++n]=999999999;
}

int part(int st, int dr)
{
	int i,j,m;
	long p,aux;
	m=(st+dr)>>1;
	p=v[m];
	i=st-1;
	j=dr+1;
	while(1)
	{
		do{++i;}while(v[i]<p);
		do{--j;}while(v[j]>p);
		if(i<j)
		{
			aux=v[i];
			v[i]=v[j];
			v[j]=aux;
		}
		else
			return j;
	}
}

void quick(int st, int dr)
{
	int p;
	if(st<dr)
	{
		p=part(st,dr);
		quick(st,p);
		quick(p+1,dr);
	}
}

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();
	quick(1,n);
	rez();
	return 0;
}