Pagini recente » Istoria paginii runda/inca_inca_vacanta_ix/clasament | Cod sursa (job #1836430) | Cod sursa (job #2668831) | Cod sursa (job #1545679) | Cod sursa (job #2616537)
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
short getBound(short target, short v[], short size, bool up) {
if (target >= v[size - 1]) return size - 1;
if (target <= v[0]) return 0;
short max = size - 1, pivot = size/2, min = 0;
while (pivot != min && pivot != max) {
if (target == v[pivot]) return pivot;
if (target > v[pivot]) min = pivot;
else max = pivot;
pivot = (max + min) / 2;
}
if (up) return max;
else return min;
}
int main()
{
fstream f("nrtri.in", ios::in);
short n;
f >> n;
short* b = new short[n];
for (int i = 0; i < n; i++) f >> b[i];
f.close();
f.open("nrtri.out", ios::out);
sort(b, b + n);
int total = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
short up = getBound(b[i] + b[j], b, n, false), down = getBound(abs(b[i] - b[j]), b, n, true);
total += up - down + 1;
if (i <= up && i >= down) total--;
if (j <= up && j >= down) total--;
}
}
f << total / 6;
f.close();
}