JEDNAKOS - JEDNAKOST
Tác giả: ladpro98
Ngôn ngữ: Pascal
program jednakos;
uses math,sysutils;
const maxn=1 shl 12;
maxm=1 shl 13;
fi='';
pow:array[0..8] of longint = (1,10,100,1000,10000,100000,1000000,10000000,100000000);
var a,len,num:array[0..maxn] of longint;
check:array[0..maxn,0..maxm] of boolean;
f:array[0..maxn,0..maxm] of longint;
res,d:longint;
s:ansistring;
procedure input;
var inp:text;
i,j:longint;
begin
assign(inp,fi);
reset(inp);
readln(inp,s);
for i:=length(s) downto 1 do
begin
if s[i]='=' then
begin
res:=StrToInt(copy(s,i+1,length(s)-i));
d:=0;
for j:=1 to i-1 do
begin
if (s[j]='0') then len[j]:=len[j-1]+1
else len[j]:=0;
if len[j]<=6 then
begin
inc(d);
a[d]:=ord(s[j])-48;
end;
end;
break;
end;
end;
check[0,0]:=true;
f[0,0]:=0;
for j:=1 to res do
begin
check[0,j]:=true;
f[0,j]:=maxn;
end;
for i:=1 to length(s) do
begin
num[i]:=10*num[i-1]+a[i];
if num[i]>res then
begin
for j:=i to length(s) do
num[j]:=-1;
break;
end;
end;
close(inp);
end;
function dp(i,j:longint):longint;
var k,t:longint;
begin
if check[i,j] then exit(f[i,j]);
if num[i]=j then
begin
check[i,j]:=true;
f[i,j]:=0;
exit(0);
end;
t:=0;
check[i,j]:=true;
f[i,j]:=maxn;
for k:=i downto 1 do
begin
t:=pow[i-k]*a[k]+t;
if t>j then break;
f[i,j]:=min(f[i,j],dp(k-1,j-t)+1);
end;
exit(f[i,j]);
end;
begin
input;
write(dp(d,res));
end.