Cod sursa(job #909960)

Utilizator Anca_PaneaPanea Anca Anca_Panea Data 10 martie 2013 18:11:31
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb


using namespace std;
#include<cstdio>
#include<algorithm>

int v[3000],n,s;
int cautare(int s,int d,int val)
    {

        if(s<=d)
        {
            int m=(s+d)/2;
            if(v[m]==val)
            {
                while(v[m+1]==val)
                    m++;
                return m;
            }
            if(v[m]<val && v[m+1]>val)
                return m;
            if(v[m]>val && v[m-1]<val)
                return m-1;
            if(v[m]>val)
                return cautare(s,m-1,val);
            return cautare(m+1,d,val);
        }
    }

int main()
{   int i,j;

    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        scanf("%d",v+i);
    sort(v+1,v+n+1);
    for (i=1;i<n;i++)
        for (j=i+1;j<n;j++)
            s=s+cautare(j+1,n,v[i]+v[j])-j;
      printf("%d",s);
    return 0;
}