Cod sursa(job #759522)

Utilizator cosminx2003Cosmin Clapon cosminx2003 Data 18 iunie 2012 14:50:34
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define N 800

using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

int v[N];

int bin(int n, int val) {
    int i, step;
    for (step = 1; step < n; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < n && v[i + step] <= val)
           i += step;
    return i;
}



int main() {
	int i,j,n,k = 0,x;

	f>>n;
	for(i = 0; i < n; i++)
		f>>v[i];
	
	sort(v,v+n);

	for(i = 0; i < n-2; i++) {
		for(j = i+1; j < n-1; j++) {
			x = bin(n,v[i]+v[j]);
			if(v[x] <= (v[i]+v[j]))
				k += (x - j > 0) ? (x-j) : 0;
			else
				k += (x-j-1 > 0) ? (x-j-1) : 0;
		}
	}

	g<<k;

	return 0;
}