Cod sursa(job #157681)

Utilizator firewizardLucian Dobre firewizard Data 13 martie 2008 10:49:18
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
int i,j,k,a[805],n,x;
long p=0;
int bs(int low,int value)
{
    int max=n;
  while (low<max)   
  {
      int mid=(low+max)/2;
      if(a[mid]<value)
      low=mid+1;
      else max =mid;
  }
  if(value==a[max])return max;
  if(value<a[max])return max-1; 
  if(value>a[n]) return n;
  if(value<a[n]) return n-1;
}

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=bs(j+1,a[i]+a[j]);
    p=p+k-j;}    
    printf("%ld",p);
    return 0;
}