Pagini recente » Cod sursa (job #1103400) | Cod sursa (job #1790534)
#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;
}