Mai intai trebuie sa te autentifici.
Cod sursa(job #2035314)
Utilizator | Data | 9 octombrie 2017 10:41:57 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.98 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
const int Dim = 801;
int a[Dim];
int n;
void ReadArray();
void Rezolvare();
int BinarySearch(int l, int r, int vl, int vr);
int main()
{
ReadArray();
Rezolvare();
}
void ReadArray()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> a[i];
}
void Rezolvare()
{
sort (a + 1, a + n + 1);
int nr = 0;
for(int i = 1; i <= n - 2; ++i)
for(int j = i + 1; j <= n - 1; ++j)
{
if (BinarySearch(j + 1, n, a[i], a[j]) != 0)
nr += BinarySearch(j + 1, n, a[i], a[j]) - j;
}
fout << nr;
}
int BinarySearch(int l, int r, int vl, int vr)
{
int mid;
int s = vl + vr;
while (l <= r)
{
mid = ( l + r ) / 2;
if (a[mid] <= s)
return mid;
if (a[mid] > s)
r = mid - 1;
}
return 0;
}