Cod sursa(job #844898)

Utilizator h2g2Ford Prefect h2g2 Data 29 decembrie 2012 22:10:45
Problema Numarare triunghiuri Scor 20
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.72 kb
var v:array[1..800] of integer;
n,i,aux,t,mid,hi,lo,j:integer;
f,g: text;

begin
  assign(f,'nrtri.in'); reset(f);
  assign(g,'nrtri.out'); rewrite(g);
  read(f,n);

  for i:=1 to n do read(f,v[i]);

  for i:=1 to n-1 do
    for j:=i+1 to n do
      if v[i]>v[j] then begin aux:=v[i]; v[i]:=v[j]; v[j]:=aux; end;

  for i:=1 to n-2 do
    for j:=i+1 to n-1 do begin
      hi:=n+1;
      lo:=j;
      while hi-lo>1 do begin
        mid:=(hi+lo) div 2;
        if v[mid]<=v[i]+v[j] then lo:=mid
                             else hi:=mid;
      end;
      {writeln('pentru pozitiile ',i,' si ',j,', lo = ',lo);}
      if (v[lo]<=v[i]+v[j]) then t:=t+lo-j
      
    end;
  write(g,t);
  close(f);
  close(g);
end.