Pagini recente » Cod sursa (job #1776703) | Cod sursa (job #1809554) | Cod sursa (job #2069702) | Cod sursa (job #962845) | Cod sursa (job #803364)
Cod sursa(job #803364)
#include<stdio.h>
#define Nmax 801
#define swap(a,b) a^=b^=a^=b
int V[Nmax], N, sol;
int get_piv(int st, int dr) {
int i = st-1, j = dr+1, val = V[(st+dr)/2];
while(1) {
do { i++; } while(V[i] < val);
do { j--; } while(V[j] > val);
if(i<j)
swap(V[i],V[j]);
else
return j;
}
}
void quick_sort(int st, int dr) {
if(st<dr) {
int pivot;
pivot = get_piv(st,dr);
quick_sort(st, pivot-1);
quick_sort(pivot+1, dr);
}
}
int binary_search(int val) {
int putere, i;
for(putere=1; putere<=N; putere<<=1);
for(i=1; putere; putere>>=1)
if(i+putere<=N && V[i+putere]<=val)
i+=putere;
return i;
}
int main() {
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
int i, j, k, poz;
scanf("%d",&N);
for(i=1; i<=N; i++)
scanf("%d",&V[i]);
quick_sort(1,N);
for(i=1; i<=N-1; i++)
for(j=i+1; j<=N; j++) {
poz = binary_search(V[i]+V[j]);
sol+=(poz-j);
}
printf("%d\n",sol);
return 0;
}