Pagini recente » Cod sursa (job #872860) | Cod sursa (job #774033) | Cod sursa (job #1757652) | Cod sursa (job #3178727) | Cod sursa (job #628313)
Cod sursa(job #628313)
#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXN 800
#define MODUL(a) ((a) < 0 ? (-(a)) : (a))
int v[MAXN], n;
using namespace std;
int findge(int key, int li, int lf) {
// imposibil
if (li > lf) {
return -1;
}
// ar trebui sa fie in dreapta
if (v[lf] < key) {
return -1;
}
// toate sunt bune
if (v[li] >= key) {
return li;
}
int m = (li + lf) / 2;
if (v[m] < key) {
return findge(key, m + 1, lf);
} else {
// Posibil asta, dar cauta si dincolo.
int candidate = findge(key, li, m - 1);
return candidate == -1 ? m : candidate;
}
}
int findle(int key, int li, int lf) {
// imposibil
if (li > lf) {
return -1;
}
// ar trebui sa fie in stanga
if (v[li] > key) {
return -1;
}
// toate sunt bune
if (v[lf] <= key) {
return lf;
}
int m = (li + lf) / 2;
if (v[m] > key) {
return findle(key, li, m - 1);
} else {
// Posibil asta, dar cauta si in partea cealalta
int candidate = findle(key, m + 1, lf);
return candidate == -1 ? m : candidate;
}
}
int main()
{
ifstream in("nrtri.in");
ofstream out("nrtri.out");
in >> n;
for (int i = 0; i < n; ++i) {
in >> v[i];
}
std::sort(v, v + n);
int sol = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (i != j) {
int plow = findge(v[j] - v[i], j + 1, n - 1);
int phigh = findle(v[i] + v[j], j + 1, n - 1);
if (plow != -1 && phigh != -1) {
sol += phigh - plow + 1;
}
}
}
}
out << sol << "\n";
in.close();
out.close();
return 0;
}