Pagini recente » Cod sursa (job #1540922) | Cod sursa (job #507342) | Cod sursa (job #1934179) | Cod sursa (job #2872140) | Cod sursa (job #788714)
Cod sursa(job #788714)
#include <cstdio>
#include <algorithm>
#define maxN 805
using namespace std;
FILE *f = fopen ("nrtri.in","r");
FILE *g = fopen ("nrtri.out","w");
int n, a[maxN], SOL;
void read()
{
fscanf (f, "%d", &n);
for (int i = 1; i <= n; i++)
fscanf (f, "%d", &a[i]);
sort (a + 1, a + n + 1);
}
int bsearch(int i, int val)
{
int lo = i, hi = n, mid;
while (lo <= hi) {
mid = (lo + hi) / 2;
if (a[mid] > val)
hi = mid - 1;
else
lo = mid + 1;
}
if (a[mid] > val)
mid--;
if (val >= a[mid])
return mid;
return -1;
}
void solve()
{
for (int i = 1; i <= n - 2; i++)
for (int j = i + 1; j <= n - 1; j++) {
int sum = a[i] + a[j];
int poz = bsearch(j + 1, sum);
if (poz != -1)
SOL += poz - (j + 1) + 1;
}
fprintf (g, "%d\n", SOL);
}
int main()
{
read();
solve();
fclose(f);
fclose(g);
return 0;
}