Cod sursa(job #157483)

Utilizator firewizardLucian Dobre firewizard Data 13 martie 2008 01:11:10
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>
int i,j,k,a[805],n,x,mid;
long p=0;
int bs(int low,int value)
{
       int high = n+1;
       while (low < high) {
           mid = (low + high)/2;
           if (a[mid] < value)
               low = mid + 1; 
           else
                //can't be high = mid-1: here A[mid] >= value,
                //so high can't be < mid if A[mid] == value
                high = mid; 
       }
       // high == low, using high or low depends on taste 
       if (low < n&&a[low] == value)
           return low; // found
       else
           return n;     
}
int cautare(int p, int u)
{
  int m;
  m=(p+u)/2;
  while (p<=u){
      if ((a[m]<=a[i]+a[j] && a[m+1]>a[i]+a[j]) || (a[m]<=a[i]+a[j] && m==n-1))
		  return m;
	  else if (a[m]<=a[i]+a[j] && a[m+1]<=a[i]+a[j]) {
		  p=m+1; 
		  m=(p+u)/2;
	  }
	  else {
		  u=m-1; 
		  m=(p+u)/2;
		  }  
  }
  return 0;
}


int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    scanf("%d\n",&n);
    for(i=1;i<=n;i++)
    scanf("%d ",&a[i]);
    
    for(i=1;i<=n-1;i++)
    for(j=i+1;j<=n;j++)
    if(a[i]>a[j])
    x=a[i];
    a[i]=a[j];
    a[j]=x;
    
    for(i=1;i<=n-2;i++)
    for(j=i+1;j<=n-1;j++)
    {k=cautare(j+1,a[i]+a[j]);
    p=p+k-j+2;}    
    printf("%ld",p);
    return 0;
}