Cod sursa(job #2074038)

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

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

void cautare(int l, int r, int suma, int v[])
{
  int m = (l+r)/2;
  int p = l - 1;
  while (l <= r) {
    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;
  for (int i = 0; i < n - 2; i++)
    for(int j = i + 1; j < n - 1; j++) {
      int suma = a[i] + a[j];
      nr += cautare(j+1, n-1, suma, v) - j;
    }
  g << n;
  g.close();
}