Cod sursa(job #189983)

Utilizator crusRus Cristian crus Data 19 mai 2008 16:06:13
Problema Numarare triunghiuri Scor 55
Compilator c Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <stdio.h>
#include <stdlib.h>
#define input "nrtri.in"
#define output "nrtri.out"
#define nmax 2000
long n,v[nmax],a[nmax],b[nmax];
long sol;
void read()
{
 int i;
 freopen(input,"r",stdin);
 scanf("%ld",&n);
 for (i=1;i<=n;i++) scanf("%ld",&v[i]);
}
void merge(long ls,long ld)
{
 long n1,n2,i,i1,i2;
 if (ls<ld)
    {
     int k=(ls+ld)/2;
     merge(ls,k); merge(k+1,ld);
     n1=0; n2=0;
     for (i=ls;i<=k;i++)
	 {
	  n1++;
	  a[n1]=v[i];
	 }
     for (i=k+1;i<=ld;i++)
	 {
	  n2++;
	  b[n2]=v[i];
	 }
     k=ls; i1=1; i2=1;
     while (i1<=n1 && i2<=n2)
	   if (a[i1]>b[i2])
	      {
	       v[k]=b[i2]; k++; i2++;
	      }
	      else
	      {
	       v[k]=a[i1]; k++; i1++;
	      }
     while (i1<=n1)
	   {
	    v[k]=a[i1]; k++; i1++;
	   }
     while (i2<=n2)
	   {
	    v[k]=b[i2]; k++; i2++;
	   }
    }
}
long bs1(long k)
{
 long ls=1,ld=n+1,mij;
 while (ls<=ld)
       {
	mij=(ls+ld)/2;
	if (v[mij]>=k && v[mij-1]<k) return mij;
	   else
	   if (v[mij]<k) ls=mij+1;
	      else ld=mij-1;
       }
 return 0;
}
long bs2(long k)
{
 long ls=1,ld=n+1,mij;
 while (ls<=ld)
       {
	mij=(ls+ld)/2;
	if (v[mij]<=k && v[mij+1]>k) return mij+1;
	   else
	   if (v[mij]<k) ls=mij+1;
	      else ld=mij-1;
       }
 return 0;
}
void solve()
{
 long i,j,s1,s2,l1,l2;
 merge(1,n);
 v[n+1]=v[n]+v[n-1]+10;
 v[0]=-1;
 for (i=1;i<=n;i++)
     for (j=i+1;j<=n;j++)
	 {
	  s1=v[j]-v[i];
	  s2=v[j]+v[i];
	  l1=bs1(s1);
	  l2=bs2(s2);
	  sol+=l2-l1;
	  if (v[i]>=s1 && v[i]<=s2) sol--;
	  if (v[j]>=s1 && v[j]<=s2) sol--;
	 }
}
void write()
{
 freopen(output,"w",stdout);
 printf("%ld",sol/3);
}
int main()
{
 read();
 solve();
 write();
 return 0;
}