Cod sursa(job #211220)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 1 octombrie 2008 13:06:35
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>
FILE *f1, *f2;
int l[100];

void sort(int li, int ls);
void intercl(int li, int ls, int mij);
int cauta(int li, int ls, int x);


int main()
{
  int i, j, n, cont=0, p;
  f1=fopen("nrtri.in", "r");
  f2=fopen("nrtri.out", "w");
  fscanf(f1, "%d", &n);
  for (i=0; i<n; i++)
    fscanf(f1, "%d", &l[i]);
  sort(0, n-1);
  for (i=0; i<n; i++)
    for (j=i+1; j<n; j++)
    {
      p=cauta(0, n-1, l[i]+l[j]-1);
      if ((p-j-1)>0)
	cont+=p-j-1;
    }//for j
  fprintf(f2, "%d", cont);
  fclose(f1);
  fclose(f2);
  return 0;
}//main

void sort(int li, int ls)
{
  int mij;
  if (li<ls)
  {
    mij=(li+ls)/2;
    sort(li, mij);
    sort(mij+1, ls);
    intercl(li, ls, mij);
  }//if
}//sort

void intercl(int li, int ls, int mij)
{
  int i1=li, i2=mij+1, ib=li, b[100], t;
  while ((i1<=mij)&&(i2<=ls))
    if (l[i1]<l[i2])
      b[ib++]=l[i1++];
    else
      b[ib++]=l[i2++];
  for (t=i1; t<=mij; t++)
    b[ib+t-i1]=l[t];
  for (t=i2; t<=ls; t++)
    b[ib+t-i2]=l[t];
  for (t=li; t<=ls; t++)
    l[t]=b[t];
}//intercl

int cauta(int li, int ls, int x)
{
  int mij;
  while (li<ls)
  {
    mij=(li+ls)/2;
    if (x<l[mij])
      ls=mij;
    else
      li=mij+1;
  }//while
  return li;
}//cauta