Pagini recente » Borderou de evaluare (job #2703850) | Borderou de evaluare (job #1765724) | Borderou de evaluare (job #1811985) | Borderou de evaluare (job #1468192) | Cod sursa (job #466017)
Cod sursa(job #466017)
#include <stdio.h>
int a[1024], n;
int main() {
freopen("nrtri.in", "r", stdin);
freopen("nrtri.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
if (a[i] > a[j]) {
a[i] ^= a[j] ^= a[i] ^= a[j];
}
int ret = 0;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j) {
//A = a[i]
//B = a[j]
//C = ?
//A + B >= C
//C >= B - A
//C >= A - B
//=> max(A-B, B-A) <= C <= A + B
int A = a[i];
int B = a[j];
int lim = A - B;
if (lim < B - A)
lim = B - A;
int Lim = A + B;
int p = 0, P = 0;
for (int k = 512; k > 0; k /= 2) {
//asta trebuie sa fie mai mare sau egal decat lim
if (((p^k) <= n) && (a[p^k] < lim))
p ^= k;
//asta trebuie sa fie mai mic sau egal decat Lim
if (((P^k) <= n) && (a[P^k] <= Lim))
P ^= k;
}
++p;
int interval = P - p + 1; // p , p + 1, p + 2 ... P
if (p <= i && i <= P)
--interval;
if (p <= j && j <= P)
--interval;
if (interval > 0)
ret += interval;
}
//COMB(3,2) = 3*2 / 1*2 = 3
printf("%d\n", ret/3);
return 0;
}