Cod sursa(job #2072329)

Utilizator Robert_VRVRobert Vadastreanu Robert_VRV Data 21 noiembrie 2017 19:03:53
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");

const int DIM = 800;
int n, x[1 + DIM];

int bin(int st, int dr, int Max)
{
  if (st <= dr)
  {
    int m = (st + dr) / 2;
    if (x[m] <= Max)
      return m - st + 1 + bin(m + 1, dr, Max);
    else
      return bin(st, m - 1, Max);
  }
  return 0;
}

int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> x[i];
  fin.close();
  sort(x + 1, x + n + 1);
  int sol = 0;
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      sol += bin(j + 1, n, x[i] + x[j]);
  fout << sol << '\n';
  return 0;
}