Cod sursa(job #2954722)

Utilizator Pop_EmilPal Tamas Pop_Emil Data 15 decembrie 2022 10:24:48
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <algorithm>
#include <stdio.h>
using namespace std;

int N, t[802], rez = 0;
FILE *in = fopen("nrtri.in", "r"), *out = fopen("nrtri.out", "w");

void _read()
{
    fscanf(in, "%d", &N);
    for(int i = 1; i <= N; ++i)
        fscanf(in, "%d", &t[i]);
}

int bins(int L, int R, int val)
{
    int M;
    while (L <= R){
        M = (L + R) / 2;

        if (val < t[M])
            R = M - 1;
        else if (val > t[M])
            L = M + 1;
        else {
            while (t[M + 1] == val)
                ++M;
            return M;
        }
    }
    return R;
}

int main()
{
    _read();

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

    int x;
    for(int i = 1; i <= N - 2; ++i)
        for(int j = i + 1; j <= N - 1; ++j){
           x = bins(j + 1, N, t[i] + t[j]);
           rez += x - j;
         }

    fprintf(out, "%d", rez);
    return 0;
}