Pagini recente » Cod sursa (job #2394930) | Cod sursa (job #1896471) | Cod sursa (job #701331) | Cod sursa (job #904094) | Cod sursa (job #895923)
Cod sursa(job #895923)
#include <stdio.h>
#include <stdlib.h>
#define MAX 800
void quicksort(int x[],int first,int last){
int pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j--;
if(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
int cauta(int v[], int poz, int start, int finish)//cea mai mare pozitie pt care v[a]+v[b]>=v[med]
{
int med=(start+finish)/2;
while (start<=finish){
if (poz>=v[med]&& v[med+1]>poz) return med;
else
if (poz>=v[med]){
start=med+1;
med=(start+finish)/2;
}else{
finish=med-1;
med=(start+finish)/2;
}
}
return -1;
}
int main()
{
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
int v[MAX];
int n,i;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d ", &v[i]);
quicksort(v,1,n);
i = 0;
int nr = 0;
for (int a=0;a<=n-3;a++)
for (int b=a+1;b<=n-2;b++){
int start=b+1;
int final1=n ;
int c=cauta(v, v[a]+v[b],start,final1);
if (c>b){
int aux=c-b;
nr+=aux;
}
}
printf("%d", nr);
return 0;
}