Pagini recente » Cod sursa (job #951136) | Cod sursa (job #1746062) | Cod sursa (job #505484) | Cod sursa (job #2623513) | Cod sursa (job #1795075)
#include <iostream>
#include <fstream>
#define NMAX 801
#define RADIX_SIZE 8
#define get_byte(x) ((x >> (RADIX_SIZE * byte)) & 0xFF)
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int A[NMAX], n;
void CountSort(int A[], int B[], int byte)
{
int length = (1 << RADIX_SIZE);
int _count[length];
int indx[length];
for (int i = 0; i < length; i++)
_count[i] = 0;
for (int i = 1; i <= n; i++)
_count[get_byte(A[i])]++;
indx[0] = 1;
for (int i = 1; i < length; i++)
indx[i] = indx[i - 1] + _count[i - 1];
for (int i = 1; i <= n; i++)
B[indx[get_byte(A[i])]++] = A[i];
}
void RadixSort(int A[], int n)
{
int *temp = new int[n + 1];
for (int i = 0; i < 4; i++)
if (i % 2 == 0)
CountSort(A,temp,i);
else
CountSort(temp,A,i);
delete[] temp;
}
int binar(int x, int key)
{
int i = 0, step;
for (step = 1; step <= key; step <<= 1);
for (; step; step >>= 1)
if (x + i + step <= n && A[x + i + step] <= key)
i += step;
return i + x;
}
int main()
{
in >> n;
for (int i = 1; i <= n; i++)
in >> A[i];
in.close();
RadixSort(A, n);
int ind;
long long int nr = 0;
for (int i = 1; i <= n - 2; i++)
for (int j = i + 1; j <= n - 1; j++)
{
ind = binar(j + 1, A[i] + A[j]);
if (A[ind] >= A[i] + A[j])
nr += (long long)(binar(j + 1, A[i] + A[j]) - j);
}
out << nr << "\n";
return 0;
}