Cod sursa(job #2074047)

Utilizator AndreiHrsAndrei Hristescu AndreiHrs Data 24 noiembrie 2017 00:54:53
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<iostream>
#include<fstream>
using namespace std;

void insertionSort(int v[], int n)
{
  for (int i = 1; i < n; i++)
  {
      int j = i - 1;
      int x = v[i];
      while (j >= 0 && x < v[j]) {
        v[j+1] = v[j];
        j--;
      }
      v[j+1] = x;
    }
}

int cautare(int l, int r, int suma, int v[])
{
  int m;
  int p = l - 1;
  while (l <= r) {
    m = (l+r)/2;
    if (v[m] <= suma) {
      p = m;
      l = m + 1;
    }
    else {
      r = m - 1;
    }
  }
  return p;
}

int main()
{
  ifstream f("nrtri.in");
  ofstream g("nrtri.out");
  int n;
  f >> n;
  int v[801];
  for (int i = 0; i < n; i++)
    f >> v[i];
  f.close();
  insertionSort(v, n);
  int nr = 0, suma;
  for (int i = 0; i < n - 2; i++)
    for(int j = i + 1; j < n - 1; j++) {
      suma = v[i] + v[j];
      nr +=  cautare(j+1, n-1, suma, v) - j;
    }
  g << nr;
  g.close();
}