Cod sursa(job #3141282)

Utilizator not_anduAndu Scheusan not_andu Data 13 iulie 2023 14:18:30
Problema Factorial Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
/*

Fie laturile unui triunghi: a, b, c

! Realtia unui Triunghi: a + b > c

*/


#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

#define INFILE "nrtri.in"
#define OUTFILE "nrtri.out"
#define VMAX 801

ifstream fin (INFILE);
ofstream fout (OUTFILE);

int n;
int aux, v[VMAX];

void rezolvare(){

    int st, dr, mij, cnt = 0, sol = 0;

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

            st = j + 1, dr = n;
            sol = -1;

            while(st <= dr){

                mij = (st + dr) / 2;

                if(v[mij] <= v[i] + v[j] && sol < mij){
                    sol = mij;
                }
                if(v[mij] <= v[i] + v[j]){
                    st = mij + 1;
                }
                else{
                    dr = mij - 1;
                }

            }
            
            if(sol != -1){

                cnt += sol - j;

            }

        }
    }

    fout << cnt << '\n'

}

void read(){

    fin >> n;

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

    }

    // afisare();

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

    // afisare();

    rezolvare();

}

int main(){
    read();
    return 0;
}