Cod sursa(job #458075)

Utilizator loginLogin Iustin Anca login Data 22 mai 2010 21:52:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
# include <fstream>
# include <iostream>
# include <algorithm>
using namespace std;
int n, sol, v[808], S, D;

void read()
{
	ifstream fin ("nrtri.in");
	fin>>n;
	for (int i=1;i<=n;++i)
		fin>>v[i];
	sort(v+1, v+n+1);
}

void cata_dr(int st, int dr, int x)
{
	if(st==dr)
	{
		if (v[st]<=x && st>D)
			D=st;
		return;
	}
	int m=(st+dr)/2;
	if (v[m]<=x)
	{
		if (m>D)D=m;
		cata_dr(m+1, dr, x);
	}
	else
		cata_dr(st, m, x);
}

void solve ()
{
	int s;
	for (int i=1;i<n-1;++i)
		for (int j=i+1;j<n;++j)
		{
			s=v[i]+v[j];
			D=0;
			cata_dr(j+1, n, s);
			if (D)sol+=D-j;
		}
}

int main ()
{
	read ();
	solve ();
	ofstream fout ("nrtri.out");
	fout<<sol;
	return 0;
}