Cod sursa(job #151677)

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

int a[nmax],n;
int cauta(int st,int dr,int val)
{
// varianta mai 'putin' recursiva 
int mij;
 while( st<=dr )
{
 mij=(st+dr)/2;
  if((a[mij]<=val && a[mij+1]>val) || (a[mij]<=val && mij+1<n))
  return mij;
  else
         if(a[mij]>val)
         dr=mij-1;
         else
         if(a[mij]<=val && a[mij+1]<=val)
         st=mij+1;
         }
         return 0;
}

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

    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;
    int m=n-1,poz;
    
    for(i=1; i<m; ++i)    
     for(j=i+1; j<=m; ++j){
             poz=cauta(j+1,n,a[i]+a[j]);
            // printf("1:%d %d %d\n",i,j,poz);
             if(poz>j){
            // printf("2:%d %d %d\n",i,j,poz);
             solfin+=poz-j;}
             }
    
    printf("%d\n",solfin);
    
    return 0;
}