Pagini recente » Monitorul de evaluare | Cod sursa (job #176029) | Cod sursa (job #1002938) | Cod sursa (job #1241925) | Cod sursa (job #63864)
Cod sursa(job #63864)
#include <stdio.h>
#include <assert.h>
#include <algorithm>
using namespace std;
enum { maxn = 801, maxv = 30001 };
int n;
int len[maxn];
int first[maxv * 2]; //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 * 2; i++)
{
while(len[pos] < i && pos < n)
pos++;
first[i] = pos;
//printf("first[%d] %d\n", i, first[i]);
}
}
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;
//printf("i %d j %d ans %d\n", i, j, ans);
}
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;
}