Cod sursa(job #115627)

Utilizator gigi_becaliGigi Becali gigi_becali Data 16 decembrie 2007 18:43:45
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
using namespace std;
#include <cstdio>
#include <algorithm>
#define maxn 801

int main()
{
	int a[maxn], n; // stiva e mai rapida decat variabilele globale! ATENTIE sizeof(stiva)<1mb pt linux...pt borland <64kb parca
	int i, j, k,cnt;
	freopen("nrtri.in","r",stdin);
	scanf("%d\n", &n); //citesc n
	for(i=1;i<=n;++i) scanf("%d ", a+i); //citesc a[i]
	
	sort(a+1, a+n+1); // sortez crescator

	int nr=0; 

	for(i=1;i<n-1;++i)
		for(j=i+1;j<n;++j) // aleg 2 pozitii i<j
		{
			// si calculez in O(logn) cate triunghiuri se pot forma cu cele 2 folosind o cautare binara
			// am folosit o cautare binara mai smenoasa si mai performanta (de 3-4 ori mai rapida)
			// ideea este sa fac salturi de 2^k 
			
			for(k=j+1, cnt=(1<<10); cnt ; cnt>>=1)
				if(k+cnt<=n)
					if(a[i]+a[j]>a[k+cnt]) k+=cnt;
		
			
			if(a[i]+a[j]>a[j+1]) nr+=k-j+1;
						
		}


	freopen("nrtri.out","w",stdout);	
	printf("%d\n", nr); //afisez solutia
	return 0;
}