Cod sursa(job #727020)

Utilizator NikitaUtiuNichita Utiu NikitaUtiu Data 27 martie 2012 18:13:55
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;

int n;
int bete[800];

int solve(const int&, const int&);

int main(void) {
	ifstream fin("nrtri.in");
	fin >> n;
	for(int i = 0; i < n; ++i)
		fin >> bete[i];
	fin.close();
	
	int sum = 0; sort(bete, bete+n);
	for(int i = 0; i < n - 1; ++i)
		for(int j = i + 1; j < n; ++j)
			sum += solve(i, j);
	
	ofstream fout("nrtri.out");
	fout << sum;
	fout.close();
}

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 && bete[pos + step] <= bete[x] + bete[y])
			pos += step;
	return pos - y;
}