Pagini recente » Cod sursa (job #1082816) | Cod sursa (job #604425) | Cod sursa (job #2448827) | Cod sursa (job #2225285) | Cod sursa (job #63712)
Cod sursa(job #63712)
#include <stdio.h>
#include <assert.h>
#include <algorithm>
using namespace std;
enum { maxn = 801, maxv = 30001 };
int n;
int len[maxn];
int first[maxv]; //first of magnitude >= i in sorted array len[]
int ans;
void precalc()
{
int i, pos;
std::sort(len, len + n);
pos = 0;
for(i = 0; i < maxv; i++)
{
while(len[pos] < i && pos < n)
pos++;
first[i] = pos;
}
}
void calc()
{
int i, j, sub;
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++)
{
assert(len[j] >= len[i]);
if(len[i] >= len[j] - len[i]) //must subtract both
sub = 2;
else //must only subtract j
sub = 1;
ans += first[ len[i] + len[j] + 1 ] - first[ len[j] - len[i] ] - sub;
}
assert(ans >= 0);
assert((ans % 3) == 0);
ans /= 3;
}
int main()
{
int i;
FILE *f = fopen("nrtri.in", "r");
if(!f) return 1;
fscanf(f, "%d", &n);
for(i = 0; i < n; i++)
fscanf(f, "%d", &len[i]);
fclose(f);
f = fopen("nrtri.out", "w");
if(!f) return 1;
precalc();
calc();
fprintf(f, "%d\n", ans);
fclose(f);
return 0;
}