Cod sursa(job #2624088)

Utilizator darkeagleDaniel Popescu darkeagle Data 4 iunie 2020 14:48:10
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;

int v[802], n;
int cautare(int p, int u,int i , int j)
{
  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))
		  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;
}
int main() {


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

 
int i, j, k;
scanf("%d",&n);
for(i = 1; i <= n; i++) {
	scanf("%d", &v[i]);
}
int ok, aux;

do {

ok = 1;
 for(i = 1; i < n ; i++) {
 	if(v[i] > v[i+1]) {

 		aux = v[i];
 		v[i+1] = v[i];
 		v[i] = aux;
 		ok = 0;
 	}
 }



} while(ok == 0);




int nr = 0, i1, j1;

for(i = 1; i <= n-2; i++) {
	for(j = i+1; j <= n-1 ; j++) {
		 nr +=  cautare(1,n,i,j) - j;

	}
}

printf("%d",nr);



return 0;
}