Cod sursa(job #449957)

Utilizator veliki.velicuVelicu Stefan veliki.velicu Data 7 mai 2010 14:22:40
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<iostream>
#include<fstream>
using namespace std;

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

int n, v[800];

int binar(int x)
{
	int i, pas = 1<<16;
	for(i=0 ; pas != 0 ; pas /= 2)
		if(i+pas <= n && v[i+pas]<=x)
			i += pas;
	return i;
}

int main()
{
	int i, j, k, nr=0, aux; 
	in>>n;
	for(i=1; i<=n; i++)
		in>>v[i];
	for(i=1; i<n; i++)
		for(j=i+1; j<=n; j++)
			if(v[i]>v[j])
			{
				aux = v[i];
				v[i] = v[j];
				v[j] = aux;
			}	
	for(i=1; i<=n-1; i++)
		for(j=i+1; j<=n; j++)
		{
			/*
			for(k=j+1; k<=n, v[k]<=v[i]+v[j]; k++)
				nr++;
			*/
			k = binar(v[i]+v[j]);
			if(k>j)
				nr += k-j;
		}
	out<<nr;
	return 0;
}