Cod sursa(job #33829)

Utilizator floringh06Florin Ghesu floringh06 Data 19 martie 2007 20:47:02
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
using namespace std;

#include <cstdio>
#include <cassert>
#include <algorithm>

#define FIN "nrtri.in"
#define FOUT "nrtri.out"
#define NMAX 801

int N, a[NMAX];

int binsearch(int i, int j)
{
  int t, step, val = a[i] + a[j];

  for (step = 1; step <= N; step <<= 1);
  for (t = j; step; step >>= 1)
    if (t + step <= N && a[t + step] <= val)
      t += step;
  return t - j;
}

int
 main ()
{
  int ct = 0;
  
  freopen ("nrtri.in", "rt", stdin);
  freopen ("nrtri.out", "wt", stdout);
  
  scanf ("%d",&N);
  for (int i = 1; i <= N; ++ i)
    scanf ("%d",&a[i]);
  sort (a+1,a+N+1);
  for (int i = 1; i <= N-1; ++ i)
    for (int j = i + 1; j <= N; ++ j)
      ct += binsearch(i, j);
      
  printf ("%d\n",ct);
  return 0;
}