Cod sursa(job #153398)

Utilizator abcabcIon Popescu abcabc Data 10 martie 2008 15:10:33
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#define N 812
int v[N];
int rez,i,j,k,n;
int caut(int p, int u, int i)
{
	int m,n,j;
	j=p;
	n=u;
	m=(p+u)/2;
	//printf(" de la%d pana %d ", p, u);
	while (p<=u)
	{
		//printf(" m=%d %d", m,v[m]);
		//printf(" pt %d %d\n " ,v[i],v[j]);
		if ((v[m]<=v[i]+v[j] && v[m+1]>v[i]+v[j]) || (v[m]<=v[i]+v[j] && m==n))
			return m; 
		else 
			if (v[m]<=v[i]+v[j] && v[m+1]<=v[i]+v[j])
			{
				p=m+1; 
				m=(p+u)/2;
			}
			else 
			{
				u=m-1; 
				m=(p+u)/2;
			} 
	}
  return 0;
}


int main()
{
	int inj,gata,aux;
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w",stdout);
	scanf("%d", &n);
	for(i=1;i<=n;++i)
		scanf("%d", &v[i]);
	inj=n;
	while(inj>1)
	{
		inj/=2;
		do{
			gata=1;
			for(i=1;i<=n-inj;i++)
				if(v[i]>v[i+inj])
				{
					aux=v[i];
					v[i]=v[i+inj];
					v[i+inj]=aux;
					gata=0;
				}
		}
		while(!gata);
	} 
	
	for (i=1;i<n-1;++i)
		for (j=i+1;j<n;++j)
		{
			k=caut(j,n,i);
			//printf(" %d %d",k,v[k]);
			rez+=(k-j);
			//printf(" rez=%d \n", rez);
		}
	printf("%d\n", rez);
	return 0;
}