Cod sursa(job #2446325)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 7 august 2019 19:21:40
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
using namespace std;

int v[801], n, triunghiuri;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

void sortare(int v[], int n) {
    for(int i = 2; i <= n; i++) {
        int p = i;
        while(p > 1 && v[p-1] > v[p]) {
            int aux = v[p-1];
            v[p-1] = v[p];
            v[p] = aux;
            p--;
        }
    }
}

int cb(int v[], int st, int dr, int nr) {
    int a = st-1;
    if(nr >= v[dr])
        return dr-a;
    else if(nr < v[1])
        return 0;
    else
        while(st < dr) {
            int m = (st+dr) / 2;
            if(v[m] <= nr)
                st = m+1;
            else
                dr = m;
        }

    if(v[st] > nr)
        st--;
    return st-a;
}

int main() {
    f >> n;
    for(int i = 1; i <= n; i++)
        f >> v[i];

    sortare(v, n);

    for(int i = 1; i < n-1; i++)
        for(int j = i+1; j < n; j++) {
            int poz = cb(v, j+1, n, v[i]+v[j]);
            triunghiuri += poz;
        }

    g << triunghiuri;
}