Cod sursa(job #33786)

Utilizator floringh06Florin Ghesu floringh06 Data 19 martie 2007 20:11:26
Problema Numarare triunghiuri Scor 45
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.79 kb

type vect = array[1..802] of integer;

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

  procedure part(left,right:integer; var stst,stdr,drst,drdr:integer);
   var piv:integer;
       i,j:integer;
       aux:integer;
     begin
      piv:=a[(left+right) div 2];
      i:=left-1;
      j:=right+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:=left; drdr:=right;
        if i=j then begin stdr:=j-1; drst:=i+1; end
          else begin stdr:=j; drst:=i; end;
     end;

 procedure qsort(left,right:integer);
   var stst,stdr,drst,drdr:integer;
    begin
     if left<right then
      begin
       part(left,right,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
  begin
   read(fi,a[i]);
  end;
 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;
    dr:=n;
    z:=x+y;
    while st<=dr do
     begin
      mj:=(st+dr) div 2;
      if z<=a[mj] then dr:=mj-1
       else st:=mj+1;
     end;
    if mj<=n-1 then
    if (z>=a[mj+1]) then
        inc(mj);
    if (z<a[mj]) then
       dec(mj);
    if z=a[mj] then
     begin
      while (z=a[mj]) and (mj<=n) do
       inc(mj);
      dec(mj);
     end;
    if z>=a[n] then mj:=n;
    if z<a[j+1] then mj:=j;
    ntri:=ntri+mj-j;
//    writeln(fo,a[i],' ',a[j],' ',a[mj],' Adun:',mj-j);
  end;
writeln(fo,ntri);
close(fo);
end.