Cod sursa(job #1891087)

Utilizator Storm_FireFox1Matei Gardus Storm_FireFox1 Data 23 februarie 2017 18:48:34
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 800;

int v[NMAX + 1], n, n2;

int cautbin1(int x)
{
    int sol = 0;
    for(int i = n2; i > 0; i/=2)
    {
        if(sol + i <= n && v[sol + i] <= x)
        {
            sol += i;
        }
    }
    return sol;
}

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
    int c, p;
    c = 0;
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i];
    }
    qsort(v, n, sizeof(int), compare);
    for(int i = 2; i <= n; i++)
    {
        for(n2 = 1; n2 * 2 <= n; n2*=2)
        {
        }
        p = cautbin1(v[i - 1] + v[i]);
        c += p - i;
    }
    fout << c - 1;
    return 0;
}