Cod sursa(job #2839372)

Utilizator indraznet09Surugiu Dragos indraznet09 Data 25 ianuarie 2022 20:35:03
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<iostream>
#include<vector>
#include<fstream>
#include<algorithm>

// condition for a valid triangle:   a + b > c

int _binary_search(const std::vector<int>& arr, int left, int right, int x, int y) {
    int best = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // std::cout << "Eu sunt mid: " << mid << "\n";
        // std::cout << "Eu sunt left: " << left << " " <<
        // "Eu sunt right: " << right << "\n";
 
        if(arr[x] + arr[y] >= arr[mid]) {
            best = mid;
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    //in case we don't find any value return -1
    // std::cout << "Eu sunt x: " << x << " Eu sunt y: " << y << "\n";
    // std::cout << "Eu sunt best: " << best << "\n";
    if(best <= y) {
        return -1;
    }
    return best;
}


int main() {

    int n;  // nr bete
    std::vector<int> values;

    std::ifstream in("nrtri.in");
    std::ofstream out("nrtri.out");

    in >> n;

    while(n--) {
        int tmp;
        in >> tmp;
        values.push_back(tmp);
    }

    sort(values.begin(), values.end());
    int res = -2;

    // for(const auto& x: values)
    //     std::cout << x << " ";
    // std::cout << "\n\n";

    int counter = 0;

    for(size_t i = 0 ; i < values.size() - 1; ++i) {
        for(size_t j = i + 1; j < values.size(); ++j) {
            res = _binary_search(values, 0, values.size() - 1, i, j);
            if(res != -1) {
                counter++;
                // std::cout << i << " " << j << " " << res << "\n";
                // out << i << " " << j << " " << res << "\n";
                // std::cout << counter << "\n";
            }
        }
    }

    out << counter << "\n";

    in.close();
    out.close();

    return 0;
}