LQDDIV - Phân tập

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxs=65536;
      max=16000000;
type ar=array[0..maxs] of longint;
var n,m,m1,m2,i,j,k,sum,t,num,q,rem,temp,re:longint; dem:int64;
    a:array[0..31] of longint;
    b:array[0..15] of longint;
    p:array[0..16] of longint;
    f,g,sl:ar;
    tr:array[0..max] of longint;
    npos:longint;

procedure rf;
var i:longint;
begin
     assign(input,fi);
     reset(input);
     p[0]:=1;
     for i:=1 to 16 do p[i]:=p[i-1] shl 1;
     readln(n);
     m:=n div 2-1;
     m1:=p[m+1]-1;
     sum:=0;
     for i:=0 to m do
     begin
          read(a[i]);
          sum:=sum+a[i];
     end;
     m:=n-n div 2-1;
     for i:=0 to m do
     begin
          read(b[i]);
          sum:=sum+b[i];
     end;
     m2:=p[m+1]-1;
     close(input);
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re,' ',dem);
     close(output);
end;

procedure sort(l,r:longint);
var x,y,i,j:longint;
begin
     i:=l; j:=r; x:=f[(i+j) div 2];
     repeat
           while f[i]<x do i:=i+1;
           while f[j]>x do j:=j-1;
           if i<=j then
           begin
                y:=f[i]; f[i]:=f[j]; f[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function bs(x:longint;var num:longint):longint;
var l,r,m,y,re,t,u,i:longint;
begin
     l:=1; r:=npos; num:=0; y:=-1; re:=maxlongint; bs:=re;
     while l<=r do
     begin
          m:=(l+r) shr 1;
          if f[m]=x then break;
          if f[m]<x then l:=m+1
          else r:=m-1;
     end;
     if rem=0 then
     begin
          for i:=m-1 to m+1 do
              if (i>0) and (i<=npos) and (abs(f[i]-x)<re) then
              begin
                   re:=abs(f[i]-x);
                   y:=f[i];
              end;
          if y<>-1 then
          begin
               bs:=re*2;
               t:=tr[y];
               num:=sl[t];
               if re<>0 then
               begin
                    if (2*x-y<0) or (2*x-y>max) then exit;
                    t:=tr[2*x-y];
                    if t>0 then num:=num+sl[t];
               end;
          end;
     end
     else
     begin
          for i:=m-2 to m+2 do
              if (i>0) and (i<=npos) then
              begin
                   if f[i]<=x then
                   begin
                        if x-f[i]<re then
                        begin
                             re:=abs(f[i]-x);
                             y:=f[i];
                        end;
                   end
                   else
                   begin
                        if f[i]-1-x<re then
                        begin
                             re:=f[i]-x-1;
                             y:=f[i];
                        end;
                   end;
              end;
          if y<>-1 then
          begin
               bs:=2*re+1;
               t:=tr[y];
               num:=num+sl[t];
               if (2*x+1-y<0) or (2*x-y+1>max) then exit;
               t:=tr[2*x+1-y];
               if t>0 then num:=num+sl[t];
          end;
     end;
end;

begin
     rf;
     for i:=1 to m1 do
     begin
          k:=i; j:=0;
          while k>0 do
          begin
               if k and 1=1 then f[i]:=f[i]+a[j];
               j:=j+1;
               k:=k shr 1;
          end;
     end;
     sort(0,m1);

     g:=f;
     npos:=1;
     fillchar(f,sizeof(f),0);
     f[1]:=0; tr[0]:=1; sl[1]:=1;
     for i:=1 to m1 do
         if g[i]=g[i-1] then inc(sl[npos])
         else
         begin
              inc(npos);
              f[npos]:=g[i];
              tr[g[i]]:=npos;
              sl[npos]:=1;
         end;

     re:=maxlongint-10; dem:=0; q:=sum div 2; rem:=sum mod 2;
     m2:=m2 shr 1;
     for i:=0 to m2 do
     begin
          k:=i; j:=0; temp:=0;
          while k>0 do
          begin
               if k and 1=1 then temp:=temp+b[j];
               j:=j+1;
               k:=k shr 1;
          end;
          t:=bs(q-temp,num);
          if t<re then
          begin
               re:=t;
               dem:=num;
          end
          else
          begin
               if t=re then dem:=dem+num;
          end;
     end;
     wf;
end.

Download