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.
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