Cod sursa(job #2742835)

Utilizator DragosC1Dragos DragosC1 Data 21 aprilie 2021 22:35:31
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;

int a[801], n, nr;

void read() {
    int i;
    ifstream f("nrtri.in");
    f >> n;
    for (i = 1; i <= n; i++)
        f >> a[i];
    f.close();
}

void solve() {
    int i, j, c, st, dr, mij, k;
    sort(a + 1, a + n + 1);
    for (i = 1; i <= n - 2; i++)
        for (j = i + 1; j <= n - 1; j++) {
            c = a[i] + a[j];
            st = j + 1, dr = n, k = -1;
            while (st <= dr) {
                mij = (st + dr) / 2;
                if (a[mij] <= c) {
                    st = mij + 1;
                    k = mij;
                }
                else dr = mij - 1;
            }
            if (k != -1)
                nr += k - j;
        }
}

void output() {
    ofstream g("nrtri.out");
    g << nr;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}