Pagini recente » Cod sursa (job #172218) | Cod sursa (job #2530412) | Cod sursa (job #2836713) | Cod sursa (job #397447) | Cod sursa (job #2001381)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 2000
#define usi unsigned short int
#define este(a, b, c) (a<=b && b<=c)
usi v[NMAX], log=1, n;
FILE *fin, *fout;
usi piv(int inf, int sup){
usi st=inf, dr=sup, pivot=v[inf];
while(st<dr){
while(st<dr && pivot<=v[dr])
dr--;
v[st]=v[dr];
while(st<dr && v[st]<=pivot)
st++;
v[dr]=v[st];
}
v[st]=pivot;
return st;
}
void quick(int inf, int sup){
int m=piv(inf, sup);
if(m-1>inf)
quick(inf, m-1);
if(m+1<sup)
quick(m+1, sup);
}
usi cautare(usi x){
usi lg=log, i;
for(i=0; lg>0; lg>>=1)
if(i+lg<n && v[i+lg]<=x)
i+=lg;
if(v[i]==x)
i--;
return i+1;
}
int main(){
fin=fopen("nrtri.in", "r");
fout=fopen("nrtri.out", "w");
usi i, j, l, u, c=0, cc=0;
fscanf(fin, "%hu", &n);
for(i=0; i<n; i++)
fscanf(fin, "%hu", &v[i]);
quick(0, n-1);
///avem triunghiul cu laturi a, b, c
///daca stim valorile a si b, a<=b
/// b-a+1 <= c <= a+b-1
///cautam binar in vector aceste valori(lower si upper bound)
///si returnam nr de elem intre lower si upper-2(scadem pe a si b)
while(log<n)
log<<=1;
for(i=0; i<n-2; i++)
for(j=i+1; j<n-1; j++){
u=cautare(v[i]+v[j]+1);
c+=u-j-1;
cc=c;
}
fprintf(fout, "%d", c);
fclose(fin);
fclose(fout);
return 0;
}