Cod sursa(job #1790534)

Utilizator mdiannnaMarusic Diana mdiannna Data 28 octombrie 2016 12:58:43
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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];

}



/*

int cautare(int p, int u)
{
  int m;
  m=(p+u)/2;
  while (p<=u){
      if ((v[m]<=v[i]+v[j] && v[m+1]>v[i]+v[j]) || (v[m]<=v[i]+v[j] && m==n-1))
    return m;
   else if (v[m]<=v[i]+v[j] && v[m+1]<=v[i]+v[j]) {
    p=m+1;
    m=(p+u)/2;
   }
   else {
    u=m-1;
    m=(p+u)/2;
    }
  }
  return 0;
}

*/

/*
for (i=0;i<n-2;++i)
    for (j=0;j<n-1;++j){
         caut(1,n);
    }
*/

void cautBin(int val, int st, int dr){
    //int m = st + (dr-st)/2;
    int m = (dr+st)/2;
   // cout << " cnt= " << cnt << endl;

    //cout << "A[" << m << "]=  " << A[m] << "   val= " << val << endl;
    //cout << " st= " << st << "  dr= " << dr << endl;

    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++;
      //      cout << A[m] << "* ";

            cautBin(val, m+1, dr);
    }
    //cout << " ------------ " << endl;

}

void alg(){

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

           // cout << "i=" << i << "  j=" << j << endl;
            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;

  //  cout << "n=" << n << endl;

	fclose(stdin);
	fclose(stdout);

    return 0;
}