记录编号	39183	评测结果	AAAAAAAAAA
题目名称	数字计算	最终得分	100
用户昵称	IMSL77	是否通过	通过
代码语言	Pascal	运行时间	0.184 s
提交时间	2012-07-05 20:26:32	内存使用	0.59 MiB

program main;
type
  integer=longint;
const
  maxn=22;
  maxT=220;
  INF=100000;
var
  n,T:integer;
  s:string;
  w:array[1..maxn,1..maxn] of integer;
  f:array[1..maxn,0..maxT] of integer;
  g:array[1..maxn,1..maxn,0..maxT] of integer;

  procedure Fopen;
  begin
    assign(input,'puzzle.in');
    reset(input);
    assign(output,'puzzle.out');
    rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input);
    close(output);
  end;

  procedure Init;
  var
    i,j:integer;
    code:integer;
    p:string;
  begin
    inc(T);
    n:=length(s);
    for i:=1 to n do
      for j:=i to n do
      begin
        p:=copy(s,i,j-i+1);
        while (length(p)>0) and (p[1]='0') do delete(p,1,1);
        if length(p)>3 then w[i,j]:=T
        else val(p,w[i,j],code);
      end;
  end;

  procedure Dp;
  var
    i,j,k,l,r,p,q:integer;
  begin
    for k:=1 to n do
      for l:=1 to n-k+1 do
      begin
        r:=l+k-1;
        for p:=0 to T do
        begin
          if w[l,r]=p then g[l,r,p]:=0 else g[l,r,p]:=INF;
          for q:=l to r-1 do
          begin
            if (w[q+1,r]>0) and (p mod w[q+1,r]=0) then
              if g[l,q,p div w[q+1,r]]+1<g[l,r,p] then
                g[l,r,p]:=g[l,q,p div w[q+1,r]]+1;
            if (w[q+1,r]=0) and (p=0) and (g[l,r,p]>1) then g[l,r,p]:=1;
          end;
        end;
      end;
    for i:=1 to n do
      for j:=0 to T do
      begin
        f[i,j]:=g[1,i,j];
        for k:=1 to i-1 do
          for p:=0 to j do
            if f[k,p]+g[k+1,i,j-p]+1<f[i,j] then
              f[i,j]:=f[k,p]+g[k+1,i,j-p]+1;
      end;
    if f[n,T-1]<INF then writeln(f[n,T-1]) else writeln(-1);
  end;
begin
  Fopen;
  repeat
    readln(s); readln(T);
    if T<0 then break;
    Init;
    Dp;
  until false;
  Fclose;
end.