Cod sursa(job #202466)

Utilizator drag0shSandulescu Dragos drag0sh Data 8 august 2008 18:59:46
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <stdio.h>
#include <algorithm>

FILE *f,*g;

using namespace std;
#define MAX 802
int v[MAX],n;
long nr,suma;

void  citire(){
  int i;
  fscanf(f,"%d",&n);
  for(i=1;i<=n;i++) fscanf(f,"%d",&v[i]);
}


int functie(int a,int b){
  return a<b;
}


void  test(){
  int i;
  for(i=1;i<=n;i++)fprintf(g,"%d ",v[i]);
}


int caut (int li, int ls)
{
 if (li>ls) return -1;   
 int m;
 m=(li+ls)/2;
 if (suma>=v[m]&&(suma<v[m+1]||m==n))return m;
 if (suma<v[m]) return caut(li, m-1);
 return caut(m+1, ls);
}



void rezolvare(){
  sort(v+1,v+n+1,functie);
  int a,b;
  long c;
  v[n+1]=32000;
  for(a=1;a<=n-2;a++)
    for(b=a+1;b<=n-1;b++){
      suma=v[a]+v[b];
      c=caut(b+1,n);
       if(c!=-1)nr+=c-b;
    }
}

int main(){
  f=fopen("nrtri.in","r");
  g=fopen("nrtri.out","w");
  citire();
  rezolvare();
  //  test();
  fprintf(g,"%ld",nr);
  
  fclose(g);
  fclose(f);
  return 0;
}