Cod sursa(job #1612240)

Utilizator PraetorGrigorosoaia Florin Praetor Data 24 februarie 2016 19:20:38
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>

int v[800], nr[90001], n;

void read() {
    int i;
    FILE *f = fopen("nrtri.in", "r");
    fscanf(f, "%d", &n);
    for (i = 0; i < n; ++i) {
        fscanf(f, "%d", &v[i]);
        nr[v[i]]++;
    }
    for(i = 2; i <= 90000; ++i)
        nr[i] = nr[i-1] + nr[i];
    fclose(f);
}


int main() {
    int i, j, dif, a, b;
    long long REZ = 0;
    read();
    for (i = 0; i < n-1; ++i)
        for(j = i+1; j < n; ++j) {
            a = v[i]; b = v[j];
            a>=b?dif=a-b:dif=b-a;
            if (dif > 0)
                REZ += (nr[a+b] - nr[dif-1]);
            else REZ += nr[a+b];
            if (a >= dif) REZ--;
            if (b >= dif) REZ--;

        }
    REZ /= 3;
    FILE *g = fopen("nrtri.out", "w");
    fprintf(g, "%lld\n", REZ);
    fclose(g);
    return 0;
}