Cod sursa(job #371085)

Utilizator ZillaMathe Bogdan Zilla Data 3 decembrie 2009 16:59:42
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>

#define Nmax 810

int n,v[Nmax],total;

void qsort(int st,int dr)
{
    int i=st,j=dr,mid=v[(st+dr)/2],tmp;
    do
        {
            while(v[i]<mid) ++i;
            while(v[j]>mid) --j;
            if(i<=j)
                {
                    tmp=v[i];
                    v[i]=v[j];
                    v[j]=tmp;
                    ++i;
                    --j;    
                }    
        }while(i<=j);
        
    if(i<dr)    qsort(i,dr);
    if(j>st)    qsort(st,j);
}

int cauta(int st,int dr,int nr)
{
    int mid,ret;
    while(st<dr)
        {
            mid=(st+dr)/2;
            if(v[mid]>nr)
                dr=mid-1;
            else
                {
                    st=mid+1;
                    ret=v[st];
                }
        }    
    return ret;
}

int main()
{
    int i;
    
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);    
    
    scanf("%d",&n);
    
    for(i=1;i<=n;++i)
        scanf("%d",&v[i]);
        
    qsort(1,n);
    
    for(i=1;i<n;++i)
        for(j=i+1;j<=n;++j)
            {
                int tmp=cauta(j+1,n,v[i]+v[j]);
                if(tmp>j)
                    total+=tmp-j; 
            }
    printf("%d\n",total);
    return 0;
}