Cod sursa(job #157995)

Utilizator firewizardLucian Dobre firewizard Data 13 martie 2008 13:29:53
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 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=j+1;
    while(a[k]<=a[i]+a[j])if(k<n+1){k++;p++;}
    else break;
    }
    printf("%ld",p);
    return 0;
}