Pagini recente » Cod sursa (job #813) | Sandbox (cutiuţa cu năsip) | zz | Cod sursa (job #652799) | Cod sursa (job #611178)
Cod sursa(job #611178)
#include <fstream.h>
int N, v[900], i, j, nr = 0, auxiliar, auxiliar2;
void citire ()
{
ifstream fin ("nrtri.in");
fin >> N;
for (i = 0; i < N; i++)
{
fin >> v[i];
}
fin.close ();
}
int c_binara (int val, int capat)
{
int i, step;
for (step = 1; step <= capat; step <<= 1);
for (i = 0; step; step >>= 1)
{
if (i + step < capat && v[i + step] <= val) i += step;
}
return i;
}
void qsort (int l1, int l2)
{
int pivot = 0, l1a = l1, l2a = l2;
if (l1 >= l2) return;
while (l1 < l2)
{
if (v[l1] > v[l2])
{
auxiliar = v[l1];
v[l1] = v[l2];
v[l2] = auxiliar;
if (pivot)
{
pivot = 0;
l2--;
}
else
{
pivot = 1;
l1++;
}
}
else
{
if (pivot) l1++;
else l2--;
}
}
qsort (l1a, l1 - 1);
qsort (l1 + 1, l2a);
}
void treaba (int index)
{
for (i = 1; i < index; i++)
{
auxiliar = v[index] - v[i];
auxiliar2 = c_binara (auxiliar, i);
while (v[auxiliar2] == auxiliar) auxiliar2--;
while (v[auxiliar2] + v[i] >= v[index] && auxiliar2 > 0) auxiliar2--;
if (v[auxiliar2] + v[i] >= v[index]) nr = nr + i;
else nr = nr + i - auxiliar2 - 1;
}
}
void scriere ()
{
ofstream fout ("nrtri.out");
fout << nr;
fout.close ();
}
int main ()
{
citire ();
if (N < 3)
{
scriere ();
return 0;
}
qsort (0, N - 1);
for (j = 2; j < N; j++)
{
treaba (j);
}
scriere ();
return 0;
}