Pagini recente » Cod sursa (job #1616268) | Cod sursa (job #182368) | Cod sursa (job #1369175) | Cod sursa (job #310840) | Cod sursa (job #353987)
Cod sursa(job #353987)
#include<cstdio>
#include<cstdlib>
#define MAXN 800
int n, cnt = 0;
int v[MAXN + 1];
void citeste()
{
int i;
FILE* fi = fopen("nrtri.in", "r");
fscanf(fi, "%d", &n);
for(i = 0; i < n; ++i) fscanf(fi, "%d", &v[i]);
fclose(fi);
}
void scrie()
{
FILE* fo = fopen("nrtri.out", "w");
fprintf(fo, "%d\n", cnt);
fclose(fo);
}
int fcmp(const void* a, const void* b)
{
return ( *(int*)a - *(int*)b );
}
int cautaBinar(int li, int ls, int suma)
{
int mij;
if(li == n) return -1;
while(ls - li > 4)
{
mij = (li + ls) / 2;
if(v[mij] > suma) ls = mij - 1;
else li = mij;
}
int k = -1;
for(int i = li; i <= ls; ++i)
if(v[i] <= suma)
k = i;
return k;
}
void rezolva()
{
int i, j, suma, k;
//sortare
qsort(v, n, sizeof(int), fcmp);
//fixam doua elemente
for(i = 0; i < n; ++i)
{
for(j = i + 1; j < n; ++j)
{
suma = v[i] + v[j];
//il cautam binar pe al treilea
k = cautaBinar(j + 1, n - 1, suma);
if(k != -1) cnt += (k - j);
}
}
}
int main()
{
citeste();
rezolva();
scrie();
return 0;
}