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.

Download