Cod sursa(job #151605)

Utilizator testelatugelu testelatu testelatu Data 8 martie 2008 14:09:30
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
#include<algorithm>
#define nmax 801
using namespace std;

int a[nmax];
int cauta(int st,int dr,int val)
{
    
    int mij=(st+dr)/2;    
    if(a[mij]<=val && a[mij+1]>val)
    return mij;
    else
        if(a[mij]>val)
       return cauta(st,mij,val);
        else 
         if(a[mij]<=val && a[mij+1]<=val)
       return cauta(mij+1,dr,val);

}

int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    
    int n;
    int aux1,aux2,solfin=0,i;

    scanf("%d",&n);
    
    for(i=1; i<=n; ++i)
    scanf("%d",&a[i]);
    
    sort(a+1,a+1+n);
    
    a[n+1]=a[n+2]=50000; //mult
    int m=n-2,poz;
    
    for(i=1; i<=m; ++i){    
             aux1=a[i];    
             aux2=a[i+1];
             poz=cauta(i+1,n,aux1+aux2);
             solfin+=poz-i-1;
             
             }
    
    printf("%d\n",solfin);
    
    return 0;
}