Cod sursa(job #1790537)

Utilizator mdiannnaMarusic Diana mdiannna Data 28 octombrie 2016 13:02:35
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 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;
    }
     cautBin(val, st, m-1);
     if(A[m] <= val){
            cnt++;
            cautBin(val, m+1, dr);
    }
}

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;
}