Cod sursa(job #1383883)

Utilizator bogdanciurezubogdan ciurezu bogdanciurezu Data 10 martie 2015 18:52:52
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <algorithm>
#define nmax 900
#define For(i, x, y) for((i) = (x); (i) <= (y); ++(i))

using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int v[nmax], n, nrtr;
int cautbin(int x){
    int st = 1, dr = n, mij, sol = 0;
    while(st <= dr){
        mij = (st + dr) / 2;
        if(v[mij] <= x){
            sol = mij;
            st = mij + 1;
        }
        else  dr = mij - 1;
    }
    return sol;
}
int main()
{int i, j, maxim;
    f>>n;
    For(i, 1, n) f>>v[i];
    sort(v + 1, v + n + 1);

    For(i, 1, n - 1){
        For(j, i + 1, n){
            maxim = cautbin(v[i] + v[j]);
            nrtr += (maxim - j);
        }
    }
    g<<nrtr<<'\n';
    return 0;
}