Hướng dẫn giải của Closest Number
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
var a,b,c:array[1..60] of byte; d,d1:array[0..9] of byte; n:byte; procedure rf; var ch:char; code,t:integer; i:byte; begin n:=0; fillchar(d,sizeof(d),0); while not eoln do begin inc(n); read(ch); val(ch,t,code); a[n]:=t; end; readln; for i:=1 to n do begin read(ch); val(ch,t,code); inc(d[t]); end; d1:=d; end; procedure max; var i,j,t:byte; kt:boolean; begin kt:=false; for i:=1 to n do begin t:=a[i]; if d[t]>0 then begin b[i]:=t; dec(d[t]); end else begin kt:=true; break; end; end; if kt then begin for j:=t+1 to 9 do if d[j]>0 then begin b[i]:=j; dec(d[j]); kt:=false; break; end; if kt then begin dec(i); inc(d[b[i]]); b[i]:=0; repeat t:=a[i]; for j:=t+1 to 9 do if d[j]>0 then begin dec(d[j]); b[i]:=j; kt:=false; break; end; if not kt then break; dec(i); inc(d[b[i]]); b[i]:=0; until not kt or (i=0); end; if i=0 then exit; while i<n do begin inc(i); for j:=0 to 9 do if d[j]>0 then begin b[i]:=j; dec(d[j]); break; end; end; end; end; procedure min; var i,j,t:byte; kt:boolean; begin kt:=false; d:=d1; for i:=1 to n do begin t:=a[i]; if d[t]>0 then begin c[i]:=t; dec(d[t]); end else begin kt:=true; break; end; end; if kt or ((a[n]=c[n]) and (a[n-1]=c[n-1])) then begin if not kt then begin inc(d[c[n]]); inc(d[c[n-1]]); c[n]:=0; c[n-1]:=0; end; kt:=true; repeat t:=a[i]; if t>0 then begin for j:=t-1 downto 0 do if d[j]>0 then begin inc(d[c[i]]); c[i]:=j; dec(d[j]); kt:=false; break; end; end; if not kt then break; dec(i); inc(d[c[i]]); c[i]:=0; until not kt or (i=0) or (c[1]=0); if kt then exit; while i<n do begin inc(i); for j:=9 downto 0 do if d[j]>0 then begin dec(d[j]); c[i]:=j; break; end; end; end; end; procedure pr; var i:byte; kt:boolean; begin fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); max; min; end; procedure wf; var i:byte; begin if b[1]=0 then write(0) else for i:=1 to n do write(b[i]); writeln; if c[1]=0 then write(0) else for i:=1 to n do write(c[i]); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N 65 char a[N], b[N], c[N]; int n, cnt[256]; bool finished; void init() { memset(cnt,0,sizeof cnt); memset(c,0,sizeof c); rep(i,n) ++cnt[b[i]]; finished = 0; } void find1(int i, bool check) { if(i == n) { if(strcmp(c,a) >= 0) { puts(c); finished = 1; } } else { if(check) { fo(j,0x30,0x39) if(cnt[j]) { --cnt[j]; c[i] = j; find1(i+1, 1); if(finished) return; ++cnt[j]; break; } } else { fo(j,a[i],0x39) if(cnt[j]) { --cnt[j]; c[i] = j; find1(i+1, j > a[i]); if(finished) return; ++cnt[j]; } } } } void find2(int i, bool check) { if(i == n) { if(strcmp(c,a) < 0) { puts(c); finished = 1; } } else { if(check) { fod(j,0x39,0x30) if(cnt[j]) { --cnt[j]; c[i] = j; find2(i+1,1); if(finished) return; ++cnt[j]; break; } } else { fod(j,a[i],i ? 0x30 : 0x31) if(cnt[j]) { --cnt[j]; c[i] = j; find2(i+1, j < a[i]); if(finished) return; ++cnt[j]; } } } } int main() { #ifndef ONLINE_JUDGE freopen( "input.txt", "r", stdin ); #endif scanf("%s%s",a,b); n = strlen(a); init(); find1(0, 0); if(!finished) puts("0"); init(); find2(0, 0); if(!finished) puts("0"); return 0; }
Code mẫu của RR
{$R+,Q+} {$Mode objFPC} uses math; const FINP=''; FOUT=''; MAXN=111; so:array['0'..'9'] of longint=(0,1,2,3,4,5,6,7,8,9); var f1,f2:text; n:longint; a,b:array[1..MAXN] of longint; temp,count:array[-1..10] of longint; 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 i:longint; s:string; begin readln(f1,s); n:=length(s); for i:=1 to n do a[i]:=so[s[i]]; readln(f1,s); for i:=1 to n do b[i]:=so[s[i]]; for i:=1 to n do inc(count[b[i]]); end; procedure solve1; var x,c,i,now:longint; ok:boolean; begin for i:=1 to n do inc(temp[a[i]]); ok:=true; for c:=0 to 9 do if count[c]<>temp[c] then ok:=false; if ok then begin for i:=1 to n do write(f2,a[i]); writeln(f2); exit; end; count[10]:=1; temp:=count; for x:=n downto 1 do begin count:=temp; for i:=1 to x-1 do dec(count[a[i]]); ok:=true; for c:=0 to 9 do if count[c]<0 then ok:=false; if not ok then continue; for c:=a[x]+1 to 9 do if count[c]>0 then begin for i:=1 to x-1 do write(f2,a[i]); write(f2,c); dec(count[c]); now:=0; for i:=x+1 to n do begin while count[now]=0 do inc(now); write(f2,now); dec(count[now]); end; writeln(f2); exit; end; end; writeln(f2,0); end; procedure solve2; var x,c,i,now:longint; ok:boolean; begin fillchar(count,sizeof(count),0); count[10]:=1; count[-1]:=1; for i:=1 to n do inc(count[b[i]]); temp:=count; for x:=n downto 1 do begin count:=temp; for i:=1 to x-1 do dec(count[a[i]]); ok:=true; for c:=0 to 9 do if count[c]<0 then ok:=false; if not ok then continue; for c:=a[x]-1 downto 0 do if (x>1) or (c>0) then if count[c]>0 then begin for i:=1 to x-1 do write(f2,a[i]); write(f2,c); dec(count[c]); now:=9; for i:=x+1 to n do begin while count[now]=0 do dec(now); write(f2,now); dec(count[now]); end; writeln(f2); exit; end; end; fillchar(count,sizeof(count),0); for i:=1 to n do inc(count[b[i]]); if count[0]>0 then begin dec(count[0]); for i:=9 downto 0 do while count[i]>0 do begin write(f2,i); dec(count[i]); end; writeln(f2); exit; end; writeln(f2,0); end; begin openF; inp; solve1; solve2; closeF; end.
Code mẫu của hieult
#include <cstdio> #include <cstring> //#include <conio.h> char s[66]; char* max(int A[]) { int b[12],t=0; for(int i = 0;i<=9;i++) b[i] = A[i]; for(int i = 9;i>=0;i--) { for(int j = t;j<b[i]+t;j++) s[j] = i+48; t+=b[i]; } s[t] = '\0'; // printf(""); return s; } char* minc(int A[]) { int b[12],t=0; for(int i = 0;i<=9;i++) b[i] = A[i]; for(int i = 1;i<=9;i++) if(b[i]>0) { s[0] = i+48; b[i]--; t++; break; } for(int i = 0;i<=9;i++) { for(int j = t;j<b[i]+t;j++) s[j] = i+48; t+=b[i]; } s[t] = '\0'; // printf(""); return s; } char* min(int A[]) { int b[12],t=0; for(int i = 0;i<=9;i++) b[i] = A[i]; for(int i = 0;i<=9;i++) { for(int j = t;j<b[i]+t;j++) s[j] = i+48; t+=b[i]; } s[t] = '\0'; // printf(""); return s; } int main() { //freopen("MCLONUM.in","r",stdin); //printf("%d\n",'0'); int a[12],n,t[12],a1[12];; char s1[66],s2[66],st[66],s1the[66]; scanf("%s %s",s1,s2); strcpy(s1the,s1); n = strlen(s2); for(int i = 0;i<10;i++) a[i] = 0; for(int i = 0;i<n;i++) a[s2[i]-48]++; for(int i = 0;i<10;i++) a1[i] = a[i]; if(strlen(s2)>strlen(s1)) printf("%s\n0\n",minc(a)); else if(strlen(s2)<strlen(s1)) printf("0\n%s\n",max(a)); else { if(strcmp(max(a),s1)<0) printf("0"); else { while(true) { int flag = 0; for(int i = 0;i<10;i++) if(a[i]>0) { flag = 1; break; } if(!flag) break; strncpy(st,s1+1,strlen(s1)); for(int i = 0;i<10;i++) t[i] = a[i]; t[s1[0]-48]--; if(a[s1[0]-48]==0 || strcmp(max(t),st)<0) { for(int i = s1[0]-48+1;i<10;i++) if(a[i]>0) { printf("%c",i+48); a[i]--; printf("%s",min(a)); break; } break; } else { printf("%c",s1[0]); a[s1[0]-48]--; strcpy(s1,st); } } } strcpy(s1,s1the); for(int i = 0;i<10;i++) { a[i] = a1[i];} printf("\n"); if(strcmp(minc(a),s1)>=0) printf("0"); else { while(true) { int flag = 0; for(int i = 0;i<10;i++) if(a[i]>0) { flag = 1; break; } if(!flag) break; strncpy(st,s1+1,strlen(s1)); for(int i = 0;i<10;i++) t[i] = a[i]; t[s1[0]-48]--; if(a[s1[0]-48]==0 || strcmp(min(t),st)>=0) { for(int i = s1[0]-48-1;i>=0;i--) if(a[i]>0) { printf("%c",i+48); a[i]--; printf("%s",max(a)); break; } break; } else { printf("%c",s1[0]); a[s1[0]-48]--; strcpy(s1,st); } } } printf("\n"); } // getch(); }
Code mẫu của ll931110
Program MCLONUM; Const input = ''; output = ''; Var a,b: array[1..60] of byte; digit: array[0..9] of byte; n: integer; sa,sb: string[60]; fi,fo: text; Procedure openfile; Begin Assign(fi, input); Reset(fi); Assign(fo, output); Rewrite(fo); End; Procedure closefile; Begin Close(fi); Close(fo); End; Procedure init; Var i: integer; Begin Readln(fi, sa); Readln(fi, sb); n:= length(sa); For i:= 1 to n do a[i]:= ord(sa[i]) - 48; End; Procedure solve1; Var i,j,k,t,ok: integer; Begin Fillchar(digit, sizeof(digit), 0); For i:= 1 to n do inc(digit[ord(sb[i]) - 48]); ok:= 0; k:= 1; While (k <= n) and (ok = 0) do Begin ok:= -1; For j:= a[k] to 9 do if digit[j] > 0 then Begin b[k]:= j; dec(digit[j]); If b[k] > a[k] then ok:= 1 else ok:= 0; break; End; inc(k); End; If ok = 1 then For i:= 0 to 9 do For t:= 1 to digit[i] do Begin b[k]:= i; inc(k); End; If ok = -1 then Begin If k = 2 then Begin Writeln(fo, 0); exit; End; k:= k - 2; inc(digit[b[k]]); While k >= 1 do Begin inc(digit[b[k]]); For j:= a[k] + 1 to 9 do if digit[j] > 0 then Begin b[k]:= j; dec(digit[j]); ok:= 1; break; End; If ok = 1 then break else dec(k); End; If k = 0 then Begin Writeln(fo, 0); exit; End; For i:= 0 to 9 do For t:= 1 to digit[i] do Begin inc(k); b[k]:= i; End; End; For i:= 1 to n do write(fo, b[i]); Writeln(fo); End; Procedure solve2; Var i,j,k,t,ok: integer; Begin Fillchar(digit, sizeof(digit), 0); For i:= 1 to n do inc(digit[ord(sb[i]) - 48]); ok:= 0; k:= 1; While (k <= n) and (ok = 0) do Begin ok:= -1; For j:= a[k] downto 0 do if digit[j] > 0 then Begin If (k = 1) and (j = 0) then break; b[k]:= j; dec(digit[j]); If b[k] < a[k] then ok:= 1 else ok:= 0; break; End; inc(k); End; If (k > n) and (b[k - 1] = a[k - 1]) then Begin ok:= -1; inc(digit[b[k - 1]]); End; If ok = 1 then For i:= 9 downto 0 do For t:= 1 to digit[i] do Begin b[k]:= i; inc(k); End; If ok = -1 then Begin If k = 2 then Begin Writeln(fo, 0); exit; End; k:= k - 2; inc(digit[b[k]]); While k >= 1 do Begin inc(digit[b[k]]); For j:= a[k] - 1 downto 0 do if digit[j] > 0 then Begin b[k]:= j; dec(digit[j]); ok:= 1; break; End; If ok = 1 then break else dec(k); End; If k = 0 then Begin Writeln(fo, 0); exit; End; For i:= 9 downto 0 do For t:= 1 to digit[i] do Begin inc(k); b[k]:= i; End; End; For i:= 1 to n do write(fo, b[i]); End; Begin openfile; init; solve1; solve2; closefile; End.
Code mẫu của khuc_tuan
// {$APPTYPE CONSOLE} {$mode delphi} var a, b : array[0..1000] of char; c, d : array['0'..'9'] of integer; xong, ok : boolean; n, i, j, k : integer; cs, ci : char; begin readln(a); readln(b); n := Length(PChar(@a)); for i:=0 to n-1 do inc(c[b[i]]); xong := false; begin d := c; for i:=0 to n-1 do dec(d[a[i]]); ok := true; for cs := '0' to '9' do if d[cs]<>0 then ok := false; if ok then begin xong := true; writeln(a); end; end; if not xong then begin for i:=n-1 downto 0 do begin d := c; ok := true; for j:=0 to i-1 do begin dec(d[a[j]]); if d[a[j]] < 0 then ok := false; end; if ok then begin for cs := succ(a[i]) to '9' do begin if d[cs] > 0 then begin for j:=0 to i-1 do write(a[j]); write(cs); dec(d[cs]); for ci := '0' to '9' do for k:=1 to d[ci] do write(ci); writeln; xong := true; break; end; end; if xong then break; end; end; if not xong then begin writeln(0); end; end; xong := false; for i:=n-1 downto 0 do begin d := c; ok := true; for j:=0 to i-1 do begin dec(d[a[j]]); if d[a[j]] < 0 then ok := false; end; if ok then begin for cs := pred(a[i]) downto '0' do begin if (cs='0') and (i=0) then continue; if d[cs] > 0 then begin for j:=0 to i-1 do write(a[j]); write(cs); dec(d[cs]); for ci := '9' downto '0' do for k:=1 to d[ci] do write(ci); writeln; xong := true; break; end; end; if xong then break; end; end; if not xong then begin writeln(0); end; end.
Bình luận