Cod sursa(job #562267)

Utilizator nicnic28nichita trita nicnic28 Data 22 martie 2011 18:55:11
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#include <algorithm>
using namespace std; ifstream in("nrtri.in"); ofstream out("nrtri.out");

const int N=801;
short v[N],n;

int caut(int x){
	int i,pos=1<<10;
	for(i=0 ; pos!=0 ; pos>>=1){
		if (i+pos<n && v[i+pos]<=x){
			i+=pos;
		}
    }
	return 1+i;
}
int verifica(){
    int nr=0,k;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
			k=caut(v[i]+v[j]);
			if(k>j)
				nr+=k-j-1;
        }
    }
    return nr;
}
int main(){
    in>>n;
	for (int i = 0; i < n; i++) {
        in>>v[i];
    }
	sort(&v[0],&v[n]);
    out<<verifica();
    return 0;
}