Cod sursa(job #1893743)

Utilizator delia_ioanaCeapa Delia Ioana delia_ioana Data 25 februarie 2017 22:57:15
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <algorithm>

using namespace std;

int cautBin(vector<int> &v, int left, int right, int maximum) {
    if (left == right || left + 1 == right) {
        return (v[right] <= maximum ? right : left);
    }

    int mid = (right - left) / 2 + left;

    if (v[mid] > maximum) {
        cautBin(v, left, mid - 1, maximum);
    } else if (v[mid] < maximum) {
        cautBin(v, mid, right, maximum);
    } else {
        return mid;
    }
}

int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);

    int n;

    scanf("%d", &n);

    vector<int> v(n);
    for (int i = 0; i < n; i ++) {
        scanf("%d", &v[i]);
    }

    sort(v.begin(), v.end());

    int counter = 0;

    for (int i = 0; i < n; i ++) {
        for (int j = i + 1; j < n; j ++) {
            if (j + 1 < n && v[j + 1] <= v[i] + v[j]) {
                int x = cautBin(v, j + 1, v.size() - 1, v[i] + v[j]) - j;
                counter += x;
            }
        }
    }

    printf("%d\n", counter);

    return 0;
}