Cod sursa(job #600949)

Utilizator mlazariLazari Mihai mlazari Data 4 iulie 2011 13:48:37
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<fstream>
#include<algorithm>

#define NMAX 803

using namespace std;

ifstream citeste("nrtri.in");
ofstream scrie("nrtri.out");

short n,b[NMAX],i,j;
int rez=0;

int cauta(int val,int st,int dr) {
  int med;
  while(st<dr) {
    med=st+(dr-st+1)/2;
    if(b[med]<=val) st=med;
    else dr=med-1;
  }
  if(b[st]<=val) return st;
  return st-1;
}

int main() {
  citeste>>n;
  for(i=0;i<n;i++)
   citeste>>b[i];
  sort(b,b+n);
  for(i=0;i<n-2;i++)
   for(j=i+1;j<n-1;j++)
    rez+=cauta(b[i]+b[j],j+1,n-1)-j;
  scrie<<rez<<'\n';
  return 0;
}