Cod sursa(job #803356)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 27 octombrie 2012 14:13:49
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#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 main() {
	
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	
	int i, j, k, sum, poz, putere;
	
	scanf("%d",&N);
	for(i=1; i<=N; i++)
		scanf("%d",&V[i]);
	
	quick_sort(1,N);
	for(putere=1; putere<=N; putere<<=1);
	
	for(i=1; i<=N-1; i++)
		for(j=i+1; j<=N; j++) {
			sum = V[i] + V[j];
			for(k = putere, poz = 0; k; k>>=1)
				if(poz+k<=N && V[poz+k]<=sum)
					poz+=k;
			if(V[poz] <= sum && poz<=N && poz!=i && poz!=j)
				sol++;
		}
		
	printf("%d\n",sol);
	
	return 0;
}