Pagini recente » Cod sursa (job #393965) | Cod sursa (job #2433947) | Cod sursa (job #1703320) | Cod sursa (job #3138318) | Cod sursa (job #132621)
Cod sursa(job #132621)
#include <stdio.h>
#define NMAX 801
int l[NMAX], n, num;
int partitie(int st, int dr)
{
int i, j, aux, pivot;
i = st - 1;
j = dr +1;
pivot = l[(st+dr)/2];
while (1)
{
do {++i;} while ( l[i] < pivot);
do {--j;} while ( l[j] > pivot);
if ( i < j)
{
aux = l[i];
l[i] = l[j];
l[j] = aux;
}
else
return j;
}
}
void sort(int st, int dr)
{
int m;
if ( st < dr)
{
m = partitie(st, dr);
sort(st, m);
sort(m+1, dr);
}
}
int caut(int s, int st, int dr)
{
int m;
while ( st <= dr)
{
m = (st+dr)/2;
if ( s == l[m])
return m;
else
if ( l[m] < s)
st = m + 1;
else
dr = m - 1;
}
return dr;
}
int main()
{
int i, j, k, s, c;
freopen("nrtri.in", "r", stdin);
freopen("nrtri.out", "w", stdout);
scanf("%d", &n);
for ( i = 1; i <= n; i++)
scanf("%d", &l[i]);
sort(1,n);
for ( i = 1; i < n; i++)
for ( j = i+1; j < n; j++)
{
s = l[i] + l[j];
c = caut(s, j+1, n);
if ( s >= l[c] && c >= j + 1)
{
if ( s == l[c] )
{
for ( k = c; l[k] == s; k++);
k--;
num += k - j;
}
else
num += c - j;
}
}
printf("%d\n", num);
return 0;
}