Cod sursa(job #1738588)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 7 august 2016 09:32:22
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int n;
vector<int> bete;

int main ()
{
	int nrc = 0;
	fin>>n;
	//bete.resize(n);
	for (int i = 1; i<=n;i++)
	{
		int x;
		fin>>x;
		bete.push_back(x);
	}
	//cout<<n<<endl;
	sort (bete.begin(), bete.end());
	//for (unsigned int i = 0; i < bete.size(); i++)
	//{
	//	cout<<bete[i] << endl;
	//}
	for (int i = 0; i <= n-3; i++)
	{
		for (int j = i+1; j <= n-2; j++)
		{
			int st = j+1;
			int dr = n-1;
			int found = false;
			while (st <= dr)
			{
								//cout<<st<<" "<<dr<<endl;

				if (st == dr && bete[i] + bete[j] < bete[st])
				{

					found = true;
					break;
				}
				else if (st == dr)
				{
					break;
				}
				int mij = st + (dr-st)/2;
				if (bete[i]+bete[j] >= bete[mij])
				{
					st = mij + 1;
				}
				else
				{
					dr = mij;
				}

			}
			if (found == true)
			{
				nrc++;	
			}
		}
	}
	fout<<nrc<<"\n";
}