Cod sursa(job #629079)

Utilizator ContraPunctContrapunct ContraPunct Data 2 noiembrie 2011 17:06:23
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<cstdio>
#include<fstream>
#include<vector>
#include <algorithm>
#define Nmax 804
using namespace std;
vector<int> bat; 
int n;
void ReadData()
{
	int i,x;
	ifstream fin("nrtri.in");
	fin>>n;
	for(i=0;i<n;i++)
	{
		fin>>x;
		bat.push_back(x);
	}
	sort(bat.begin(),bat.end());
}
void Sol()
{
	ofstream fout("nrtri.out");
	int a,b,nr=0,stg,drp,m,suma;
	for(a=0;a<n;++a)
		for(b=a+1;b<n;++b)
		{
			suma = bat[a]+bat[b];
			stg = b+1;
			drp = n-1;
			int ok = -1;
			while(stg<=drp)
			{
				m = (drp+stg)/2;
				if( suma >= bat[m] ) 
				{
					ok = m; 
					stg = m+1;
				}
				else
				{
					drp = m-1;
				}	
			}
			//printf("%d ",ok);
			if( ok == -1 )
				;
			else
				nr += (ok-b);
		}
	fout<<nr<<"\n";
}
			
int main()
{	
	ReadData();
	Sol();
	return 0;
}