Cod sursa(job #33119)

Utilizator luana_0105Fagarasan Luana luana_0105 Data 18 martie 2007 22:14:32
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
using namespace std;

#include <cstdio>
#include <algorithm>

int ct, n, c, a[801];

int binsearch(int i, int j)
{
  /*int x = j, y = n, z;
  int nr = a[i] + a[j];
  while (x <= y)
   {
     z = (x + y) / 2;
     if (a[z] >= nr)
       y = z - 1;
     else x = z + 1;
   }
  return x - j + 1;*/
  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 i, j;
  freopen ("nrtri.in","rt", stdin);
  freopen ("nrtri.out","wt", stdout);
  scanf ("%d",&n);
  for (i=1;i<=n;i++)
    scanf ("%d",&a[i]);
  sort (a+1,a+n+1);
  for (i=1;i<=n-1;i++)
    for (j=i+1;j<=n;j++)
      ct += binsearch(i, j);
  printf ("%d\n",ct);
  return 0;
}