JEDNAKOS - JEDNAKOST
Tác giả: flashmt
Ngôn ngữ: Pascal
uses math;
const maxn=1010;
oo=1000000;
var s,n,l:longint;
a:ansistring;
f:array[0..maxn,0..maxn*5] of longint;
p:array[1..4] of longint;
b:array['0'..'9'] of longint;
g:array[0..maxn,0..maxn*5] of longint;
procedure rf;
var i:longint; st:ansistring; code:integer;
begin
readln(a);
for n:=1 to length(a) do
if a[n+1]='=' then break;
st:='';
for i:=n+2 to length(a) do
st:=st+a[i];
l:=length(st);
val(st,s,code);
end;
procedure init;
var i,j:longint; c:char;
begin
p[1]:=1;
for i:=2 to 4 do p[i]:=p[i-1]*10;
for c:='0' to '9' do b[c]:=ord(c)-48;
for i:=0 to n do
for j:=0 to s do
f[i,j]:=oo;
for j:=0 to s do g[0,j]:=oo;
f[0,0]:=0;
end;
procedure pr;
var i,j,k,x:longint;
begin
for i:=1 to n do
begin
x:=0;
for j:=1 to 4 do
begin
if i<j then break;
x:=x+p[j]*b[a[i-j+1]];
for k:=x to s do
f[i,k]:=min(f[i,k],f[i-j,k-x]+1);
end;
if x=0 then
begin
g[i]:=g[i-1];
continue;
end;
j:=j+1;
if (i>=j) and (a[i-j+1]='0') then
begin
for k:=x to s do
f[i,k]:=min(f[i,k],g[i-j+1,k-x]+1);
end;
if a[i]='0' then
begin
if (i>1) and (a[i-1]='0') then
begin
for j:=0 to s do
g[i,j]:=min(g[i-1,j],f[i,j]);
end
else
begin
for j:=0 to s do
g[i,j]:=min(f[i,j],f[i-1,j]);
end;
end;
end;
if a[n]='0' then f[n,s]:=min(f[n,s],g[n,s]+1);
writeln(f[n,s]-1);
end;
begin
rf;
init;
pr;
end.