Cod sursa(job #2633182)

Utilizator denisacris03Bunea Denisa denisacris03 Data 6 iulie 2020 17:52:54
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
using namespace std;
int v[800];

int search(int n, int suma) {
    // cautam elementul cel mai mare <= decat suma
    int st = 0, dr = n-1, mij;
    while (st < dr){
        mij = (st + dr + 1)/2;
        if (suma < v[mij]){
            dr = mij-1;
        }else{
            st = mij;
        }
    }
    return st;
}

int main()
{
    int n, i, j, k, rasp;
    
    ifstream f ("nrtri.in");
    ofstream g ("nrtri.out");
    
    f >> n;
    
    for (i = 0; i < n; i++){
        f >> v[i];
    }
    rasp = 0;
    for (i = 0; i < n-2; i++){
        for (j = i+1; j < n-1; j++){
            k = search(n, v[i] + v[j]);
            if (k > j) {
                rasp += k - j;
            }
        }
    }
    
    g << rasp;
    
    f.close();
    g.close();
    return 0;
}