Cod sursa(job #1022720)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 5 noiembrie 2013 21:23:14
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int n, x;
int cnt;
int suma;
vector<int> q;

int ASDGAF(int st);

int main()
{
    is >> n;
    q.push_back(0);
    for ( int i = 1; i <= n; ++i )
    {
        is >> x;
        q.push_back(x);
    }
    sort(q.begin(), q.end());
    for ( int i = 1; i <= n - 2; ++i )
        for ( int j = i + 1; j <= n - 1; ++j )
        {
            suma = q[i] + q[j];
            cnt += ASDGAF(j) - j - 1;
        }
    os << cnt;
    is.close();
    os.close();
    return 0;
}

int ASDGAF(int st)
{
    int m, dr = n;
    bool gasit = false;
    while ( st < dr )
    {
        m = ( st + dr ) / 2;
        if ( q[m] > suma )
            dr = m - 1;
        else
        {
            st = m + 1;
            gasit = true;
        }
    }
    if ( suma >= q[dr] )
        return dr + 1;
    return dr;
}