Cod sursa(job #2279442)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 9 noiembrie 2018 16:13:47
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream> // reimplementare pentru lab ASD
#include <algorithm>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int N, A[801], i, j, cnt, mask;
int cautbin (int val, int mask) {
    int sol = 0;
    while (mask) {
        if (sol + mask <= N)
            if (A[sol + mask] <= val)
                sol += mask;
        mask >>= 1;
    }
    return min(sol, N);
}
int main() {
    f >> N;
    for (i = 1; i <= N; i++)
        f >> A[i];
    sort(A + 1, A + N + 1);
    cnt = 0;
    mask = 1;
    while (mask <= N)
        mask <<= 1;
    mask >>= 1;
    for (i = 1; i <= N; i++)
        for (j = i + 1; j <= N; j++)
            cnt += cautbin(A[i] + A[j], mask) - j;
    g << cnt;
    return 0;
}