Cod sursa(job #1498563)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 8 octombrie 2015 19:16:55
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 2000
int v[MAXN];
void myqsort(int begin,int end){
    int b=begin,e=end,aux,pivot=v[(b+e)/2];
    while(b<=e){
        while(v[b]<pivot) b++;
        while(v[e]>pivot) e--;
        if(b<=e){
            aux=v[b];
            v[b]=v[e];
            v[e]=aux;
            b++;e--;
        }
    }
    if(begin<e) myqsort(begin,e);
    if(b<end) myqsort(b,end);
}
int main(){
    FILE*fi,*fout;
    int i,j,rez,pas,n,con;
    fi=fopen("nrtri.in" ,"r");
    fout=fopen("nrtri.out" ,"w");
    fscanf(fi,"%d" ,&n);
    for(i=0;i<n;i++)
       fscanf(fi,"%d" ,&v[i]);
    myqsort(0,n-1);
    con=0;
    for(i=0;i<n-2;i++)
        for(j=i+1;j<n-1;j++){
               rez=0;
               for(pas=1<<11;pas;pas>>=1)
                  if(pas+rez<n&&v[pas+rez]<=v[i]+v[j])
                     rez+=pas;
               if(rez>j)
                  con=con+rez-j;
        }
    fprintf(fout,"%d" ,con);
    fclose(fi);
    fclose(fout);
    return 0;
}