Cod sursa(job #221332)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 15 noiembrie 2008 19:59:19
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>
FILE*fin=fopen("nrtri.in","r");
FILE*fout=fopen("nrtri.out","w");
int n,s[1001];
int main()
{
  int i,ord=0,solution=0,j,x,st,dr,mij;
  fscanf(fin,"%d",&n);
  for(i=1;i<=n;i++)
    fscanf(fin,"%d",&s[i]);
  fclose(fin);
  while(!ord)
  {
    ord=1;
    for(i=1;i<n;i++)
      if(s[i]>s[i+1])
      {
	ord=0;
	s[i]^=s[i+1]^=s[i]^=s[i+1];
      }
  }
  for(i=1;i<n-1;i++)
    for(j=i+1;j<n;j++)
    {
      x=s[i]+s[j];
      st=j+1;dr=n;
      while(st<dr-1)
      {
	mij=(st+dr)/2;
	if(s[mij]<=x) st=mij;
	else dr=mij-1;
      }
      if(s[dr]<=x) solution+=dr-j;
      else if(s[st]<=x) solution+=st-j;
    }
  fprintf(fout,"%d",solution);
  fclose(fout);
  return 0;
}