Pagini recente » Cod sursa (job #240134) | Cod sursa (job #3154246) | Cod sursa (job #1464551) | Cod sursa (job #2701518) | Cod sursa (job #33147)
Cod sursa(job #33147)
type vect = array[1..800] of integer;
var fi,fo:text;
i,j,n,x,y,z,mj,st,dr:integer;
a:vect;
ntri:longint;
procedure heapsort(n:integer);
var aux,k:integer;
begin
for i:=1 to n do
begin
j:=i;
while (j div 2<>0) and (a[j div 2]<a[j]) do
begin
aux:=a[j div 2];
a[j div 2]:=a[j];
a[j]:=aux;
j:=j div 2;
end;
end;
i:=n;
while i>1 do
begin
aux:=a[1];
a[1]:=a[i];
a[i]:=aux;
dec(i);
j:=1;
while (1>0) do
begin
k:=2*j;
if (k>i) then break;
if (k+1<=i) and (a[k+1]>a[k]) then inc(k);
if a[j]>=a[k] then break;
aux:=a[j];
a[j]:=a[k];
a[k]:=aux;
j:=k;
end;
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]);
heapsort(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;
if z>=a[n] then begin mj:=n; inc(ntri,n-j); continue; end;
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;
if z<a[mj] then
dec(mj);
if mj+1<=n then
if z>a[mj+1] then inc(mj);
if a[mj]=z then
begin
while a[mj]=z do
inc(mj);
dec(mj);
end;
if mj+1<=n then
if z>a[mj+1] then inc(mj);
if a[mj]=z then
begin
while a[mj]=z do
inc(mj);
dec(mj);
end;
if (mj=j+1) then if (z<a[mj]) then mj:=j;
ntri:=ntri+mj-j;
end;
writeln(fo,ntri);
close(fo);
end.