Editorial for JEDNAKOST


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

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.

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int L = 1000 + 10, S = 5000 + 10;
int f[L][S], s, p10[] = {1, 10, 100, 1000};
char a[L];

void enter() {
    scanf("%s", a+1);
    char * buf = strchr(a+1, '=');
    s = atoi(buf+1);
    *buf = 0;
}

void solve() {
    memset(f, 0x3f, sizeof f); f[0][0] = -1;
    int l = strlen(a+1);
    for(int i = 1; i <= l; ++i)
        for(int j = 0; j <= s; ++j) {
            if(a[i] == 0x30) f[i][j] = f[i-1][j] + (i == l);
            int tmp = 0;
            for(int k = 0; k < 4 && k < i; ++k) {
                tmp += p10[k] * (a[i-k] - 0x30);
                if(tmp <= j) f[i][j] = min(f[i][j], f[i-k-1][j-tmp] + 1);
                else break;
            }
        }
    printf("%d\n", f[l][s]);
}

int main() {
    enter();
    solve();
}

Code mẫu của ladpro98

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.

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=1001;
  MAXK=5001;
  so:array['0'..'9'] of longint=(0,1,2,3,4,5,6,7,8,9);
var
  first,last,sum,n:longint;
  s:ansistring;
  qs,qi,qd:array[1..MAXN*MAXK] of longint;
  xet:array[0..MAXK,1..MAXN] of longint;
  check:array[1..MAXN] of byte;
  f1,f2:text;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  ss:ansistring;
  code:integer;
  i:longint;
begin
  readln(f1,ss);
  s:=copy(ss,1,pos('=',ss)-1); n:=length(s);
  delete(ss,1,pos('=',ss));
  val(ss,sum,code);
  check[n+1]:=1;
  for i:=n downto 1 do
    if (check[i+1]=1) and (s[i]='0') then check[i]:=1
    else break;
end;
procedure solve;
var
  u,i,uu,ii,d,sl,x:longint;
begin
  first:=1; last:=1; qs[1]:=sum; qi[1]:=1; qd[1]:=0;
  while first<=last do
    begin
      u:=qs[first]; i:=qi[first]; d:=qd[first]; inc(first);
      if (u=0) and (check[i]=1) then
        begin
          if i<n+1 then inc(d);
          writeln(f2,d-1); exit;
        end;
      sl:=n+1-i; x:=0; ii:=i;
      for sl:=1 to sl do
        begin
          x:=x*10+so[s[ii]]; uu:=u-x; inc(ii);
          if x=0 then continue;
          if (uu<0) then break;
          if xet[uu,ii]=0 then
            begin
              xet[uu,ii]:=1;
              inc(last); qs[last]:=uu; qi[last]:=ii; qd[last]:=d+1;
            end;
        end;
    end;
end;
begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
#include <ctype.h>
//#include <conio.h>

char a[1111];
int alen,sum;

void Enter()
{
     int c;
     while(!isdigit(c=getchar()));
     alen = 0;
     do a[alen++] = c; while(isdigit(c=getchar()));
     a[alen]='\0';
     while(!isdigit(c=getchar()));
     sum = 0;
     do sum=10*sum+c-'0';while(isdigit(c=getchar()));
}

int min[5555][1025];

int tinh(int tong,int vitri)
{
    int result = 1000000000;
    int i,num,t;
    if(min[tong][vitri]) return min[tong][vitri];
    if(vitri == alen)
    {
        if(tong==0) return 0;
        else return result;
    }
    if(a[vitri]=='0')
    {
        if(vitri == alen-1)
        {
            if(tong ==0) return 1;
            else return result;
        }
        else return tinh(tong,vitri+1);
    }
    for(num=0,i=vitri;i<alen;i++)
    {
        if((num=10*num+a[i]-'0')>tong) break;
        if((t=1+tinh(tong-num,i+1))<result) result = t;
    }
    return (min[tong][vitri] = result);
}

int main()
{
   // freopen("JEDNAKOS.in","r",stdin);
    Enter();
    printf("%d\n",tinh(sum,0)-1);
    //getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program JEDNAKOS;
  Const
    input  = '';
    output = '';
    maxn = 1000;
    maxs = 5000;
    maxv = 100000000;
  Var
    c,F: array[0..maxn,0..maxs] of integer;
    last: array[0..maxn] of integer;
    a: string;
    n,s: integer;


Procedure init;
  Var
    fi: text;
    tmp,st: string;
    k,i,code: integer;
  Begin
    Assign(fi, input);
      Reset(fi);
      Readln(fi, st);
    Close(fi);

    k:= pos('=', st);
    tmp:= copy(st, k + 1, length(st) - k);
    val(tmp, s, code);

    delete(st, k, length(st) - k + 1);

    a:= '';
    k:= 0;
    For i:= 1 to length(st) do if st[i] <> '0' then
      Begin
        k:= 0;
        a:= a + st[i];
      End
    else
      Begin
        inc(k);
        If k <= 7 then a:= a + st[i];
      End;

    n:= length(a);
  End;

Procedure solve;
  Var
    st: string;
    i,j,k,x: integer;
    tmp,code: integer;
  Begin
    Fillchar(last, sizeof(last), 0);
    last[0]:= 1;

    For i:= 1 to n do
      For j:= 0 to s do F[i,j]:= maxv;

    c[0,1]:= 0;
    F[0,0]:= -1;

    For i:= 1 to n do
      Begin
        j:= i;
        st:= '';

        Repeat
          st:= a[j] + st;
          If (length(st) >= 5) and (a[j] <> '0') then break;
          val(st, x, code);

          For k:= 1 to last[j - 1] do
            Begin
              tmp:= c[j - 1,k] + x;
              If (tmp <= s) and (F[i,tmp] = maxv) then
                Begin
                  inc(last[i]);
                  c[i,last[i]]:= tmp;
                End;

              if (tmp <= s) and (F[i,tmp] > F[j - 1,c[j - 1,k]] + 1)
                then F[i,tmp]:= F[j - 1,c[j - 1,k]] + 1;
            End;

          dec(j);
        Until j = 0;
      End;
  End;

Procedure printresult;
  Var
    fo: text;
  Begin
    Assign(fo, output);
      Rewrite(fo);
      Writeln(fo, F[n,s]);
    Close(fo);
  End;

Begin
  init;
  solve;
  printresult;
End.

Code mẫu của khuc_tuan

//{$Q+,R+,S+}
// {$APPTYPE CONSOLE}
 {$mode delphi}

uses math, sysutils;

var
    buf : array[0..2000] of char;
    a : PChar;
    cur, k, inf, i, j, s, na : integer;
    f : array[0..1000,0..5000] of integer;
    next : array[0..1000] of integer;

function IFF(a : boolean; b, c : integer) : integer;
begin
    if a then IFF := b else IFF := c;
end;

begin
    readln(buf);
    for i:=0 to 2000 do if buf[i]='=' then
    begin
        buf[i] := #0;
        a := @buf;
        s := StrToInt(PChar(@buf[i+1]));
    end;
    fillchar( f, sizeof(f), $1f);
    inf := f[0,0];
    f[0,0] := 0;
    na := Length(a);
    Dec(a);
    for i:=na downto 1 do
    begin
        if (i=na) or (a[i]<>a[i+1]) then next[i] := i + 1
        else next[i] := next[i+1];
    end;
    for i:=0 to na-1 do
        for j:=0 to s do
            if f[i,j] < inf then
            begin
                cur := 0;
                for k:=IFF(a[i+1]='0', next[i+1]-1, i+1) to na do
                begin
                    cur := cur * 10 + ord(a[k]) - 48;
                    if cur > s then break;
                    if cur + j <= s then
                        f[k, cur + j] := min( f[k, cur + j], f[i,j] + 1);
                end;
            end;
    writeln( f[na, s] - 1 );    
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.