Cod sursa(job #1172260)

Utilizator azkabancont-vechi azkaban Data 17 aprilie 2014 09:55:30
Problema Numarare triunghiuri Scor 50
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.33 kb
Program triunghiuri;
var H : array [1..900] of longint;
    n,i,l,j,m : longint;
    b1,b2 : array [ 0..1 shl 17 ] of char;

function binary(j ,x : longint ) : longint ;
var stinga, dreapta, mijloc : longint;
    gasit : boolean ;
begin
      stinga:=j+1; dreapta:=n; gasit:=false;
      repeat
            mijloc:=stinga +(dreapta-stinga) div 2;
            if ((H[mijloc]>x) and (H[mijloc-1]<x))
            or (H[mijloc]=x) then begin
                                                           binary:=mijloc;
                                                           gasit:=true;
                                                       end
            else if (H[mijloc]<x) then stinga:=mijloc+1
                                  else dreapta:=mijloc-1;
      until (stinga>dreapta) or gasit;

      if stinga>dreapta then binary:=n-j
                        else
          if  H[mijloc]=x then binary:=mijloc-j
                        else binary:=mijloc-j-1;
end;


procedure swap(var x,y:longint);
     var aux:longint;
      begin
       aux:=x;
       x:=y;
       y:=aux;
      end;

procedure coboara( n, k : longint);
  var fiu : longint;
    begin
         repeat
               fiu:=0;
               if k*2<n then begin
                                  fiu:=k*2;
                                  if (k*2+1<=n) and (H[k*2+1]>H[k*2]) then fiu:=k*2+1;
                                  if H[fiu]<=H[k] then fiu:=0
                              end;
               if fiu<>0 then begin
                                    swap(H[k],H[fiu]);
                                    k:=fiu;
                              end;
         until fiu=0;
   end;


procedure heapsort(n : longint);
  var i :longint; begin
     for i:=n downto 2 do  begin
                                swap(H[1],H[i]);
                                coboara(i-1,1);
                           end;
  end;
begin
  assign(input,'nrtri.in'); settextbuf(input,b1); reset(input);
  assign(output,'nrtri.out'); settextbuf(output,b2); rewrite(output);
  readln(n); l:=0;
  for i:=1 to n do read(H[i]);
  for i:=n div 2 downto 1 do coboara(n,i);
  heapsort(n);

  for i:=1 to n-2 do begin
       for j:=i+1 to n-1 do l:=l+binary(j,h[i]+h[j]);

                           end;

  writeln(l);
  close(input);
  close(output);
end.