Cod sursa(job #157469)

Utilizator firewizardLucian Dobre firewizard Data 13 martie 2008 00:55:32
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 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 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,a[i]+a[j]);
    p=p+k-j;}    
    printf("%ld",p);
    return 0;
}