Cod sursa(job #1615773)

Utilizator bob123bobelus bob bob123 Data 26 februarie 2016 20:51:00
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int sol,n,i,v[11],poz[11],a[1001];
int cbin(int p,int u,int nr)
{
    int m=(p+u)/2;
    if(a[m]>nr) return cbin(p,m-1,nr);
           else return m;
}
void back(int k,int j)
{
    if(k<=2){
        for(int i=j+1;i<=n-1;++i){
            poz[k]=i;
            v[k]=a[i],back(k+1,i);
        }
    }
    else{
        int nr=v[1]+v[2];
        if(poz[2]==n-1){
                if(a[n]<=nr)
                    ++sol;
            }
        else {
            int p=cbin(poz[2],n,nr);
            sol=sol+(p-poz[2]);
        }
    }
}
int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    scanf("%d", &n);
    for(i=1;i<=n;++i)
        scanf("%d", &a[i]);
    sort(a+1,a+1+n);
    back(1,0);
    printf("%d", sol);
    return 0;
}