Cod sursa(job #362442)

Utilizator digital_phreakMolache Andrei digital_phreak Data 9 noiembrie 2009 19:18:49
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>

#define MAXN 1010
using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

long A[MAXN];
long N;

inline bool isTri(int x,int y,int z) {
	return ((x <= (y + z)) && (y <= (x + z)) && (z <= (x + y)));
}

int main() {
	int i,j,k1,k2,res,l;
	res = 0;
	
	fin >> N;
	for (i=0;i<N;++i) 
		fin >> A[i];
		
	for (i=0;i<N-1;++i)
		for (j=i+1;j<N;++j)
			if (A[i] > A[j]) swap(A[i],A[j]);
		
	res = 0;
		
	for (i=0;i<N;++i)
		for (j=i+1;j<N;++j) {
			for (l=1;l<N;l<<=1);
			for (k1=j;l;l>>=1) {
				if (k1 + l < N)
					if (A[k1+l] <= A[i] + A[j]) k1 += l;
			}
			
			for (l=1;l<N;l<<=1);
			for (k2=j;l;l>>=1)
				if (k2 + l < N)
					if (A[k2 + l] < abs(A[i] - A[j])) k2 += l;
			
			if (k1 == j) continue;
			if (k2 == j) k2 = j + 1;
			res += k1 - k2 + 1;
		}
	
	fout << res << "\n";

	fin.close();
	fout.close();

	return 0;
}