Cod sursa(job #1794637)

Utilizator mdiannnaMarusic Diana mdiannna Data 1 noiembrie 2016 16:10:58
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;
int n;
int A[1000];
int cnt = 0;

void citire(){
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> A[i];

}



void cautBin(int val, int st, int dr){
    int m = st + (dr-st)/2;
    //int m = (dr+st)/2;

    if(st>dr)
        return;
    if(st == dr){
        if(A[st] <= val){
            cnt++;
          //  cout << A[st] << " ";
        }
        return;
    }

     if(A[m] <= val){

            cnt+= m-st+1;
            cautBin(val, m+1, dr);
    }else
        cautBin(val, st, m-1);
}

void alg(){

    for(int i=0; i<n-2 ; i++)
        for(int j=i+1; j<n-1; j++){
            cautBin(A[i]+A[j], j+1, n-1);
    }
}

int main(){
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);

    citire();
    sort(A, A+n);

    alg();
    cout << cnt;

  	fclose(stdin);
	fclose(stdout);

    return 0;
}