Cod sursa(job #731779)

Utilizator danalex97Dan H Alexandru danalex97 Data 9 aprilie 2012 10:30:34
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define Nmax 811
#define swp(a ,b) a ^=b ^=a ^=b

ifstream F("nrtri.in");
ofstream G("nrtri.out");

int N,A[Nmax];
int co;

int solve(const int& x, const int& y) 
{
	int step, pos;
	for( step = 1; step < N - y; step <<= 1 );
	for( pos = y; step != 0; step >>= 1)
		if( pos + step < N && A[pos + step] <= A[x] + A[y])
			pos += step;
	return pos - y;
}

int main()
{
	F>>N;
	for (int i=0;i<N;++i)
		F>>A[i];
	for (int i=0;i<N-1;++i)
		for (int j=i+1;j<N;++j)
			if ( A[i] > A[j] )
				swp(A[i],A[j]);
	
	for (int i=0;i<N-1;++i)
		for (int j=i+1;j<N;++j)
			co+=solve(i,j);
	
	G<<co<<'\n';	

	F.close();
	G.close();
	return 0;
}