LQDDIV - Phân tập
Tác giả: ladpro98
Ngôn ngữ: Pascal
program LQDDIV;
uses math;
const maxn=33;
fi='';
type pair=record
x,y:int64;
end;
var n,lim,d:longint;
res,count,sum,m:int64;
a:array[1..maxn] of longint;
s:array[1..1 shl (maxn shr 1)] of int64;
procedure Enter;
var inp:text;
i:longint;
begin
assign(inp,fi);reset(inp);
readln(inp,n);
for i:=1 to n do begin
read(inp,a[i]);
inc(a[i],a[i]);
inc(sum,a[i]);
end;
close(inp);
lim:=n div 2;
m:=sum div 2;
res:=high(int64);
end;
procedure findAbs(key:int64; var p:pair);
var l,r,m:longint;
begin
l:=1;r:=d;
while abs(l-r)<>1 do begin
m:=(l+r) shr 1;
if s[m] = key then begin
p.x:=s[m];p.y:=s[m];
exit;
end;
if s[m] < key then l:=m
else r:=m;
end;
if abs(s[l]-key)=abs(s[r]-key) then begin
p.x:=s[l];p.y:=s[r];
exit;
end;
if abs(s[l]-key)<abs(s[r]-key) then begin
p.x:=s[l];p.y:=s[l];
end
else begin
p.x:=s[r];p.y:=s[r];
end;
end;
function findL(key:int64):longint;
var l,r,m,k:longint;
begin
l:=1;r:=d;
while l<=r do begin
m:=(l+r) shr 1;
if s[m]>=key then begin
k:=m;
r:=m-1;
end
else l:=m+1;
end;
exit(k);
end;
function findR(key:int64):longint;
var l,r,m,k:longint;
begin
l:=1;r:=d;
while l<=r do begin
m:=(l+r) shr 1;
if s[m]<=key then begin
k:=m;
l:=m+1;
end
else r:=m-1;
end;
exit(k);
end;
procedure update(k:int64);
var l,r:longint;
p:int64;
t:pair;
begin
findAbs(m-k,t);
p:=2*(t.x+k)-sum;
if abs(p)<res then begin
res:=abs(p);
l:=findL(t.x);
r:=findR(t.y);
count:=r-l+1;
end
else
if abs(p) = res then begin
l:=findL(t.x);
r:=findR(t.y);
inc(count,r-l+1);
end;
end;
procedure Gen(i:longint; k:int64);
begin
if i>lim then begin
inc(d);
s[d]:=k;
exit;
end;
Gen(i+1,k);
Gen(i+1,k+a[i]);
end;
procedure Back(i:longint; k:int64);
begin
if i>n then begin
update(k);
exit;
end;
back(i+1,k);
back(i+1,k+a[i]);
end;
procedure Sort(l,r:longint);
var i,j:longint;
p,t:int64;
begin
if l>=r then exit;
i:=l;j:=r;
p:=s[random(r-l+1)+l];
repeat
while s[i]<p do inc(i);
while s[j]>p do dec(j);
if i<=j then begin
if i<j then begin
t:=s[i];
s[i]:=s[j];
s[j]:=t;
end;
inc(i);dec(j);
end;
until i>j;
Sort(l,j);sort(i,r);
end;
begin
Enter;
Gen(1,0);
Sort(1,d);
Back(lim+1,0);
write(res div 2,' ',count div 2);
end.