Hướng dẫn giải của JEDNAKOST
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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.
Bình luận