Cod sursa(job #1743145)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 17 august 2016 17:27:33
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f1=fopen("nrtri.in","r");
FILE *f2=fopen("nrtri.out","w");
int n,v[1001],i,j,s,nrsol,ind;
int cautB(int val,int st,int dr){
    int mij;
    mij=(st+dr)/2;
    if (st>dr) return -1;
    if (v[mij]<=val && v[mij+1]>val) return mij;
    if (v[mij]<=val) return cautB(val,mij+1,dr);
      else
        return cautB(val,st,mij-1);
}
int main(){
   fscanf(f1,"%d",&n);
   for (i=1;i<=n;i++){
    fscanf(f1,"%d",&v[i]);
   }
   sort(v+1,v+n+1);
   v[n+1]=30001;
   fclose(f1);
   for (i=1;i<=n-2;i++)
     for (j=i+1;j<=n-1;j++){
          s=v[i]+v[j];
          ind=cautB(s,j+1,n);
          if (ind>j) nrsol=nrsol+ind-j;
     }
    fprintf(f2,"%d",nrsol);
   fclose(f2);
   return 0;
}