Cod sursa(job #121390)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 8 ianuarie 2008 16:59:04
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<stdio.h>
int n,v[801],a[801];
long s;

void merge(int st, int dr)
{
int ok,g,m,i,j,k;
if(st<dr)
	{
	m=(st+dr)/2;
	merge(st,m);
	merge(m+1,dr);
	//interclasare  st-->m       m+1-->dr
	i=st;
	j=m+1;
	ok=1;
	k=0;
	while(ok)
		{
		if(v[i]<v[j])
			a[++k]=v[i++];
		else
			a[++k]=v[j++];
		if (i>m || j>dr)
			ok=0;
		}
	for(g=j;g<=dr;g++)
		a[++k]=v[g];
	for(g=i;g<=m;g++)
		a[++k]=v[g];
	k=0;
	for(i=st;i<=dr;i++)
		v[i]=a[++k];
	}
}

int bs(int st, int dr)
{
int m;
m=(st+dr)/2;
if(st>dr) return m;
if(v[m]>=s)
  if(v[m-1]>=s)
    return bs(st,m-1);
  else
    return m-1;
else
  return bs(m+1,dr);
}

int main()
{
int i,j,k;
long tr=0;
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
  scanf("%d",&v[i]);
merge(1,n);
for(i=1;i<=n-2;i++)
  for(j=i+1;j<n;j++)
    {
    s=v[i]+v[j]+1;
    k=bs(j+1,n);
    tr=tr+k-j;
    }
printf("%ld",tr);
return 0;
}