限制背包
Program P1014;
const
maxv=120000;
n=6;
var
a:array[1..6] of longint;
i,j,k,l,v:longint;
f:array[0..maxv] of boolean;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure CompletePack(cost:longint);
var
i:longint;
begin
for i:=cost to v do
f[i]:=f[i] or f[i-cost];
end;
procedure ZeroOnePack(cost:longint);
var
i:longint;
begin
if cost=0 then exit;
for i:=v downto cost do
begin
f[i]:=f[i] or f[i-cost];
end;
end;
procedure main;
var
i,j,k,l,sum,p:longint;
begin
v:=v div 2;
for i:=1 to n do
begin
if i*a[i]>=v then
begin
CompletePack(i);
continue;
end;
sum:=1;
k:=0;
while (a[i]-sum+1>0) do begin inc(k); sum:=sum*2; end;
dec(k);
sum:=1;
for j:=0 to k-1 do
begin
ZeroOnePack(sum*i);
sum:=sum*2;
end;
ZeroOnePack((a[i]-sum+1)*i);
if f[v] then
begin
writeln('Can be divided.');
exit;
end;
end;
if not(f[v]) then writeln('Can''t be divided.')
else writeln('Can be divided.')
end;
begin
for i:=1 to n do read(a[i]);
j:=1;
while (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]<>0) do
begin
writeln('Collection #',j,':');
fillchar(f,sizeof(f),false);
f[0]:=true;
v:=0;
for i:=1 to n do inc(v,i*a[i]);
if (v mod 2=1) then writeln('Can''t be divided.')
else
begin
main;
end;
writeln;
for i:=1 to n do read(a[i]);
inc(j);
end;
end.