Cod sursa(job #525529)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 25 ianuarie 2011 14:17:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b) {
	return a<b;
}

ifstream aa("nrtri.in");
ofstream ss("nrtri.out");
int n,i,x[8010],j,pas,p,k,nrtri;
int main() {
	aa >> n;
	for (i=1;i<=n;++i) {
		aa >> x[i];
	}
	p=1;
	while (p<n) p*=2;
	sort(&x[1],&x[n+1],cmp);
	for (i=1;i<=n-2;++i) {
		for (j=i+1;j<=n-1;++j) {
			pas=p;
			for (k=j;pas>0;pas/=2) {
				if (x[k+pas]<=x[i]+x[j] && k+pas<=n) {
					k+=pas;
				}
			}
			nrtri+=k-j;
		}
	}
	ss << nrtri;
	return 0;
}