Cod sursa(job #1546845)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 8 decembrie 2015 19:42:35
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define DIM 805

int N, V[DIM];

int bin_search(int in, int sf, int x);

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

    scanf("%d\n", &N);

    for(int i = 1; i <= N; ++i) {
        scanf("%d", &V[i]);
    }

    int answer = 0;

    sort(V + 1, V + 1 + N);

    for(int i = 1; i < N; ++i) {
        for(int j = i + 1; j <= N; ++j) {
            int pos = bin_search(j + 1, N, V[i] + V[j]);
            if(pos > j) {
                answer += pos - j;
            }
        }
    }

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

    return 0;
}

int bin_search(int in, int sf, int x) {
    int lg = sf - in + 1;
    int p = 1;

    while(p <= lg) {
        p <<= 1;
    }

    p >>= 1;

    int pos = in - 1;

    while(p) {
        if(pos + p <= sf) {
            if(V[pos + p] <= x) {
                pos += p;
            }
        }

        p >>= 1;
    }

    return pos;
}