Pagini recente » Cod sursa (job #2984618) | Cod sursa (job #524007) | Cod sursa (job #1118370) | Cod sursa (job #2143382) | Cod sursa (job #583747)
Cod sursa(job #583747)
#include <stdio.h>
#define IN "nrtri.in"
#define OUT "nrtri.out"
#define N 801
static int v[N];
static void bubblesort(int);
static int cautbin(int, int, int);
int main(void) {
int n, i, j;
long nrtri = 0;
(void) freopen(IN, "r", stdin);
(void) freopen(OUT, "w", stdout);
(void) scanf("%d", &n);
for(i = 1; i <= n; ++i) scanf("%d", &v[i]);
bubblesort(n);
for(i = 1; i < n - 1; ++i) for(j = i + 1; j < n; ++j)
nrtri += cautbin(1, n, v[i] + v[j]) - j;
printf("%ld\n", nrtri);
return 0;
}
void bubblesort(int n) {
int sortat, i, aux;
do {
sortat = 1;
for(i = 1; i < n; ++i)
if(v[i] > v[i + 1]) aux = v[i], v[i] = v[i + 1], v[i + 1] = aux,
sortat = 0;
} while(!sortat);
}
int cautbin(int lo, int hi, int n) {
int mid;
do {
mid = lo + (hi - lo) / 2;
if(v[mid] < n) lo = mid + 1;
else hi = mid - 1;
} while(lo <= hi && v[mid] != n);
if(v[mid] > n) -- mid;
if(v[mid] == n) while(v[mid + 1] == n) ++mid;
return mid;
}