Cod sursa(job #3279338)

Utilizator 9onelostSendrescu Tudor-Gabriel 9onelost Data 22 februarie 2025 16:15:42
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>
#define DIM 1000
using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n, nrc;

int v[DIM];

int cautare(int st,int dr, int val){

    int ret = 0, mij;

    while(st<=dr){

        mij=(st+dr)/2;

        if(v[mij] <= val){

            ret = mij;

            st=mij+1;

        }

        else{

            dr=mij-1;

        }

    }

    return ret;

}

int main() {

    fin >> n;

    for(int i=1;i<=n;i++){

        fin >> v[i];

    }

    sort(v+1,v+n+1);

    for(int i=1;i<=n-2;i++){

        int l1= v[i];

        int l2=v[i+1];

        int maxval = l1+l2;

        int poz = cautare(i+2, n, maxval);

        nrc+= poz-(i+1);

    }

    fout << nrc;

    return 0;
}