Cod sursa(job #1705974)

Utilizator RazvanatorHilea Razvan Razvanator Data 21 mai 2016 10:39:57
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int v[1000];
int n;

void Read()
{
    fin>>n;
    for (int i=1;i<=n;i++) fin>>v[i];
    fin.close();
}

int caut_bin(int a,int b)
{
    int i=0,pas=1<<9;
    while (pas!=0) {
        if (i+pas<=n && v[a]+v[b]>=v[i+pas]) i+=pas;
        pas/=2;
    }
    return i;
}

int main()
{
    Read();
    sort(v+1,v+1+n);
    int s=0,x,j;
    for (int i=1;i<n;i++) {
        for (j=i+1;j<=n;j++){
            x=caut_bin(i,j);
            if (x-j>0) s+=x-j;
        }
    }
    fout<<s;
}