Cod sursa(job #303969)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 10 aprilie 2009 16:52:51
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<stdio.h>
long nr,s;
int v[804],n,i,j,z,x[804],sf,in,max,m;
void merge (long a,long b)
{
long m,i,j,u=0;
if(a>=b)
   return ;

m=(a+b)/2;
merge(a,m);
merge(m+1,b);
i=a;j=m+1;
while(i<=m && j<=b)
{
if(i==-1 && j==-1)
   break;
 else
	if(i==-1)
	{
	v[++u]=x[j];
	  j++;
	}
	else
	   if(j==-1)
	   {
	   v[++u]=x[i];
		i++;
	   }
else
{
 if(x[i]<x[j])
 {
  v[++u]=x[i];
  i++;
  if(i==m+1)
	i=-1;

 }//if
 else
	{
	v[++u]=x[j];
	j++;
	if(j==b+1)
	 j=-1;
	}
}//else mare
}//while
for(i=a;i<=b;i++)
  x[i]=v[i-a+1];
  u=0;
}
int main ()
{
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
	scanf("%d",&x[i]);
merge(1,n);
for(i=1;i<=n;i++)
  for(j=i+1;j<=n;j++)
   {
   s=x[i]+x[j];
   sf=n;
   in=j+1;
   max=0;
	while(in<=sf)
	{
	 m=(in+sf)/2;
	 if(x[m]<=s)
	 {
	  max=m;
	  in=m+1;
	 }
	 else
		sf=m-1;
	}
	if(max)
	nr=nr+max-j;
   }
printf("%ld",nr);
return 0;
}