Cod sursa(job #1705967)

Utilizator RazvanatorHilea Razvan Razvanator Data 21 mai 2016 10:27:50
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 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-1;i++) {
        for (j=i+1;j<n;j++)
            x=caut_bin(i,j);
        if (x-j>0) s+=x-j;
    }
    fout<<s;
}