Cod sursa(job #927778)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 26 martie 2013 00:40:25
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

#define Nmax 2002

char FileIn [] = { "nrtri.in" };
char FileOut [] = { "nrtri.in" };

int N, R;
int V[Nmax];

void citire(){

    ifstream f(FileIn);

    f >> N;

    for ( int i = 1; i <= N; ++i )
        f >> V[i];

    f.close();
}

void rezolva(){

    int log2;

    for ( log2 = 1; log2 <= N; log2 <<= 1 );

    for ( int i = 1; i <= N; ++i )
        for ( int j = i + 1; j < N; ++j ){

            int ab = V[i] + V[j];
            int poz = j + 1;

            if ( V[poz] > ab )
                continue;

            for ( int t = log2; t; t >>= 1 )
                if ( poz + t <= N && V[poz + t] <= ab )
                    poz += t;

            R += ( poz - j );
        }
}

void afis(){

    ofstream g(FileOut);

    g << R << "\n";

    g.close();
}

int main(){

    citire();
    sort ( V + 1, V + N + 1 );
    rezolva();
    afis();

    return 0;
}