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.

Download