Cod sursa(job #2071998)

Utilizator moltComan Calin molt Data 21 noiembrie 2017 11:54:13
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,v[801],rez;

/*int caut_bin(int st,int dr,int l1,int l2)
{
    int mij = (st + dr) / 2;
    while (st <= dr)

}*/

void caut_bin_biti(int a,int b,int i,int j)
{
    int r = 0,L = 9;
    int pas = 1 << L;
    while (pas != 0)
    {
        if (r + pas <= n && v[r + pas] <= v[i] + v[j])
            r += pas;
        pas >>= 1;
    }
    if (r >= j)
    {
        rez += r - j;
    }
}
/*int caut_bin_biti(int a,int b)
{
    r = 0;
    pas = 1 << L;  //L = floor(log2(b - a + 1))
    while (pas != 0)
           if (r + pas are proprietatea)
               r += pas;
            pas /= 2; //pas >>= 1;
     return r;
}*/

int main()
{
    in>>n;
    for (int i = 1; i <= n; ++i)
        in>>v[i];
    sort(v + 1,v + n + 1);
    for (int i = 1; i <= n - 2; ++i)
        for (int j = i + 1; j <= n - 1; ++j)
            caut_bin_biti(j + 1,n,i,j);
    out<<rez;
    return 0;
}