Cod sursa(job #1641335)

Utilizator DoubleNyNinicu Cristian DoubleNy Data 8 martie 2016 22:31:18
Problema Numarare triunghiuri Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.94 kb
type
    tabel=array[1..810] of longint;
var A,B,C,N,i,j,m,k,o:longint;
    rezerva:tabel;

procedure quick(var arr:tabel; left,right:integer);
var pivot,i,j,x:integer;
begin
     i:=left;
     j:=right;
     pivot:=arr[(left+right) div 2];
     while i<=j do
     begin
          while arr[i]  < pivot do inc(i);
          while arr[j] > pivot do dec(j);
          if i<=j then
          begin
              x:=arr[i];
              arr[i]:=arr[j];
              arr[j]:=x;
              inc(i);
              dec(j);
          end;
     end;
     if left<j then
     quick(arr,left,j);
     if i<right then
     quick(arr,i,right);
end;

procedure bsearch(a,b,low,hight:longint);
var mid:longint;
begin
        if low=hight then exit;
        mid:=low div 2 +hight div 2;
        if mid<=b then while mid<=b do inc(mid);
        if mid>hight then mid:=hight;
        if (rezerva[a]+rezerva[b]>=rezerva[mid]) then
        begin
        while (rezerva[a]+rezerva[b]>=rezerva[mid]) and (mid<=hight) do inc(mid);
              dec(mid);
              m:=m+(mid-b);
        end else if (hight-low>1) then bsearch(a,b,low,mid);

end;

Begin
      assign(input,'nrtri.in'); reset(input);
      assign(output,'nrtri.out'); rewrite(output);
      readln(input,n);
     for i:=1 to n do read(input,rezerva[i]);
      quick(rezerva,1,n);   o:=0;
   //   for i:=1 to n do write(rezerva[i],' ');
   {O(n^3)---------------------------------------
       m:=0;
       for i:=1 to n-2 do
        for j:=i+1 to n-1 do
         for k:=j+1 to n do
         begin
              A:=rezerva[i]; B:=rezerva[j]; C:=rezerva[k];
              if (A+B>=C) and (A+C>=B) and (B+C>=A) then inc(m)
              else break
         end;
     ---------------------------------------------------------}
     for i:=1 to n-1 do
     for j:=i+1 to n do
          bsearch(i,j,j,n);

      write(output,m);
      close(input);
      close(output);
End.