Cod sursa(job #234961)

Utilizator stefynr8Space Monkey stefynr8 Data 22 decembrie 2008 12:29:35
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>
#include <fstream.h>
#include <iostream.h>
#include <mem.h>
#include <math.h>
#include <string.h>

FILE *f,*g;

int n,v[801],i,j,k,c;

int cautare(int x, int y, int sum)
{
  int m,i,j,last=0;
  i=x;
  j=y;
  while (i<=j)
   {
      m=(i+j)/2;
      if (v[m]>sum)
	j=m-1;
       else
	{
	 last=m;
	 i=m+1;
	}
   }
  return last;
}

int main()
{

 freopen("nrtri.in","r", stdin);
 freopen("nrtri.out","w", stdout);

 scanf("%d", &n);
 for (i=1;i<=n;i++)
	scanf("%d", &v[i]);
 for (i=1;i<=n-1;i++)
  for (j=i+1;j<=n;j++)
	if (v[i]>v[j])
		{
		 v[0]=v[i];
		 v[i]=v[j];
		 v[j]=v[0];
		}
 for (i=1;i<=n-2;i++)
  for (j=i+1;j<=n-1;j++)
	  {
	   c=cautare(j+1,n,v[i]+v[j]);
	   if (c>0)
		k=k+c-j;
	  }
 printf("%d", k);

 return 0;
}