Pagini recente » Cod sursa (job #2433391) | Cod sursa (job #2365176) | Cod sursa (job #1473036) | Cod sursa (job #490842) | Cod sursa (job #2497438)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int const N = 1000;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int bsUltimul(int n, int LungimeBat[], int SumaLaturilor)
{
int sol = 0;
int pas = 1 << 10;
while (pas > 0)
{
if (sol + pas < n && LungimeBat[sol + pas] <= SumaLaturilor)
{
sol += pas;
}
pas /= 2;
}
return sol;
}
int bsPrimul(int n, int LungimeBat[], int SumaLaturilor)
{
int sol = bsUltimul(n, LungimeBat, SumaLaturilor - 1);
if (sol < SumaLaturilor)
{
sol++;
}
return sol;
}
int main()
{
/** Pentru a forma un triunghi:
* a + b >= c
* b + c >= a
* a + c >= b
{1}
[abs(i - j); i + j]
cautam binar numerele din interval
*/
int n;
fin >> n;
int contor = 0;
int LungimeBat[N];
for (int i = 0; i < n; i++)
{
fin >> LungimeBat[i];
}
sort(LungimeBat, LungimeBat + n);
for (int i = 0; i < n - 2; i++) // Pentru ultimele 2 nr din sir nu vom putea forma un triunghi
{
for (int j = i + 1; j < n - 1; j++) // Mergem pana la penultima cifra
{
int Dreapta = bsUltimul(n, LungimeBat, LungimeBat[i] + LungimeBat[j]);
int Stanga = j + 1;
int NrInInterval = Dreapta - Stanga + 1;
contor += NrInInterval;
}
}
fout << contor;
}