Cod sursa(job #32997)

Utilizator floringh06Florin Ghesu floringh06 Data 18 martie 2007 20:09:04
Problema Numarare triunghiuri Scor 45
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.58 kb

type vect = array[1..805] of longint;

var fi,fo:text;
    i,j,n,x,y,z,mj,st,dr:integer;
    a:vect;
    ntri:int64;

  procedure part(st,dr:integer; var stst,stdr,drst,drdr:integer);
   var i,j,piv,aux:integer;
    begin
     piv:=a[(st+dr) div 2];
     i:=st-1;
     j:=dr+1;
     while i<j do
      begin
       repeat inc(i) until a[i]>=piv;
       repeat dec(j) until a[j]<=piv;
       if i<j then
        begin
         aux:=a[i];
         a[i]:=a[j];
         a[j]:=aux;
        end;
      end;
      stst:=st; drdr:=dr;
      if i=j then
       begin
        stdr:=j-1;
        drst:=i+1;
       end
      else
       begin
        stdr:=j;
        drst:=i;
       end;
    end;

  procedure qsort(st,dr:integer);
   var stst,stdr,drst,drdr:integer;
    begin
     if st<dr then
      begin
       part(st,dr,stst,stdr,drst,drdr);
       qsort(stst,stdr);
       qsort(drst,drdr);
      end;
    end;





begin
 ntri:=0;
 assign(fi,'nrtri.in'); reset(fi);
 assign(fo,'nrtri.out'); rewrite(fo);
 readln(fi,n);
 for  i:=1 to n do
  read(fi,a[i]);
 qsort(1,n);
 for i:=1 to n-2 do
  for j:=i+1 to n-1 do
   begin
    x:=a[i];
    y:=a[j];
    st:=j+1;
    dr:=n;
    z:=x+y;
    while st<=dr do
     begin
      mj:=(st+dr) div 2;
      if z<a[mj] then dr:=mj-1;
      if z>a[mj] then st:=mj+1;
      if z=a[mj] then break;
     end;
    while a[mj]>z do
     dec(mj);
    if a[mj]=z then
     begin
      while a[mj]=z do
       inc(mj);
      dec(mj);
     end;
    inc(ntri,mj-j);
   end;
writeln(fo,ntri);
close(fo);
end.