Cod sursa(job #1009332)

Utilizator lucianRRuscanu Lucian lucianR Data 12 octombrie 2013 20:58:23
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#define N_MAX 800

using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");

int v[N_MAX], n, t[N_MAX];

void mergee(int left, int m, int right)
{
    int l = left, r = m + 1, k = 0;
    while(l <= m && r <= right)
        if(v[l] < v[r])
            t[k++] = v[l++];
        else
            t[k++] = v[r++];
    while(l <= m)
            t[k++] = v[l++];
    while(r <= right)
            t[k++] = v[r++];
    for(int i = left; i <= right; i++)
        v[i] = t[i-left];
}


void msort(int lo, int hi)
{
    if(lo < hi)
    {
        int m = (lo + hi) / 2;
        msort(lo, m);
        msort(m + 1, hi);
        mergee(lo, m, hi);
    }
}

int bsearch(int target, int not_1, int not_2)
{
    int i = not_2+1;
    while(v[i] <= target && i < n)
        i++;
    return i-not_2-1;
}

int tfind()
{
    int res = 0;
    for(int i = 0; i < n - 2; i++)
        for(int j = i+1; j < n-1; j++)
               res += bsearch(v[i] + v[j], i, j);
    return res;
}

int main()
{
    in >> n;
    for(int i = 0; i < n; i++)
        in >> v[i];
    msort(0, n-1);
    out << tfind();
    return 0;
}