Hướng dẫn giải của VM 09 Bài 06 - SỐ RÕ RÀNG
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
#include<iostream> #include<algorithm> #include<string> #include<cstdio> #define fr(a,b,c) for (a=b;a<=c;a++) #define frr(a,b,c) for (a=b;a>=c;a--) #define oo 100000000 using namespace std; int d[1501],tr[1501],ll[1501],nm; long long f[19][10][1501],g[19][1501],re[1501]; void init() { int i,j,l,x,y; fr(i,1,1500) d[i]=-1; d[1]=1; frr(i,1500,2) if (d[i]==-1) { x=i; while (d[x]==-1) { d[x]=0; tr[0]=x; y=0; while (x) { y+=(x%10)*(x%10); x/=10; } x=y; tr[x]=tr[0]; } if (d[x]) do { x=tr[x]; d[x]=1; } while (x!=i); } fr(j,0,9) { f[1][j][j*j]=1; g[i][j*j]=1; } fr(l,2,18) fr(j,0,9) fr(i,j*j,1500) { f[l][j][i]+=g[l-1][i-j*j]; g[l][i]+=f[l][j][i]; } } long long calc(long long n) { int i,j,l=0,a[22],s=0; long long nn=n,res=0; fr(i,1,nm) re[i]=0; while (nn) { a[++l]=nn%10; nn/=10; } while (l) { fr(i,0,a[l]-1) fr(j,1,nm) if (ll[j]>=s) re[j]+=f[l][i][ll[j]-s]; s+=a[l]*a[l]; l--; } fr(i,1,nm) { res+=re[i]; if (ll[i]==s) res++; } return res; } int main() { int test,i; long long n,m,lo,hi,mi; init(); fr(i,1,1500) if (d[i]) ll[++nm]=i; cin >> test; while (test--) { cin >> n >> m; m+=calc(n); lo=1; hi=oo; hi*=oo; while (lo<=hi) { mi=(lo+hi)/2; if (calc(mi)<m) lo=mi+1; else hi=mi-1; } mi--; while (mi<1 || calc(mi)<m) mi++; cout << mi << endl; } return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> const int N = 2000; using namespace std; bool isClear[N], was[N]; long long f[20][2][N]; long long n, kth; vector<int> D; int sumSqr(int x) { int ans = 0; while (x > 0) { ans += (x % 10) * (x % 10); x /= 10; } return ans; } void initialize() { isClear[1] = 1; for (int i = 2; i < N; ++i) { memset(was, 0, sizeof(was)); for (int j = i; !was[j]; j = sumSqr(j)) { was[j] = 1; if (j < i) { isClear[i] = isClear[j]; break; } } } } long long dp(int i, bool bigger, int sum) { if (i < 0) return bigger && isClear[sum]; long long &ans = f[i][bigger][sum]; if (ans != -1 ) return ans; ans = 0; for (int x = (bigger ? 0 : D[i]); x <= 9; ++x) ans += dp(i - 1, bigger | (x > D[i]), sum + x * x); return ans; } void solve() { cin >> n >> kth; long long _n = n; D.clear(); while (_n > 0) { D.push_back(_n % 10); _n /= 10; } D.resize(18); memset(f, -1, sizeof(f)); long long ans = 0; bool bigger = 0; int sum = 0; for (int i = 17; i >= 0; --i) { for (int x = (bigger ? 0 : D[i]); x <= 9; ++x) { long long now = dp(i - 1, bigger | (x > D[i]), sum + x * x); if (kth > now) { kth -= now; } else { ans = ans * 10 + x; bigger |= x > D[i]; sum += x * x; break; } } } cout << ans << '\n'; } int main() { initialize(); int nTest; cin >> nTest; while (nTest--) { solve(); } return 0; }
Code mẫu của RR
//Written by RR {$ifdef rr} {$mode objfpc} {$inline off} {$r+,q+} {$else} {$mode objfpc} {$inline on} {$r-,q-} {$endif} uses math; const FINP = ''; FOUT = ''; MAXN = 18; MAXK = 1500; isClear : array[1..MAXK] of longint=( 1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0,0,1, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0, 1,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0, 0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,0, 0,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1, 0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0, 0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0, 0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0, 0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0, 1,0,0,1,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,1,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0, 1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0, 1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,1,1, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0, 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0); var f1,f2 : text; m,n : int64; test : longint; f : array[0..18,0..1500,0..1] of int64; g : array[0..18,0..1500] of int64; a : array[0..18] 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 initf; var i,j,now,u:longint; begin fillchar(f,sizeof(f),0); fillchar(g,sizeof(g),0); f[0,0,0]:=1; u:=a[0]; g[0,0]:=1; for i:=0 to MAXN-1 do begin for j:=0 to MAXK do begin if f[i,j,0]>0 then for now:=0 to 9 do if now<a[u] then inc(f[i+1,now*now+j,1],f[i,j,0]) else if now=a[u] then inc(f[i+1,now*now+j,0],f[i,j,0]); if f[i,j,1]>0 then for now:=0 to 9 do inc(f[i+1,now*now+j,1],f[i,j,1]); end; dec(u); if u=0 then break; end; for i:=0 to MAXN-1 do for j:=0 to MAXK do if g[i,j]>0 then for now:=0 to 9 do inc(g[i+1,now*now+j],g[i,j]); end; procedure init(n:int64); var nn:int64; begin fillchar(a,sizeof(a),0); nn:=n; while (n>0) do begin inc(a[0]); a[a[0]]:=n mod 10; n:=n div 10; end; n:=nn; end; function count(n:int64):int64; var i:longint; begin init(n); initf; result:=0; for i:=1 to MAXK do if (f[a[0],i,1]+f[a[0],i,0]>0) and (isClear[i]=1) then inc(result,f[a[0],i,1]+f[a[0],i,0]); end; procedure solve; var s,i,j,now:longint; tt,sum:int64; ok:boolean; begin tt:=count(n)+m; ok:=false; s:=0; for i:=1 to MAXN do for now:=0 to 9 do begin inc(s,now*now); sum:=0; for j:=1 to 1500 do if (isClear[j]=1) and (j>=s) then inc(sum,g[18-i,j-s]); if tt>sum then dec(tt,sum) else begin if ok then write(f2,now) else if (not ok) and (now>0) then begin write(f2,now); ok:=true; end; break; end; dec(s,now*now); end; writeln(f2); end; begin openF; read(f1,test); for test:=1 to test do begin read(f1,n,m); solve; end; closeF; end.
Code mẫu của ll931110
{$MODE DELPHI} program CLEAR4; const input = ''; output = ''; maxd = 20; maxs = 81; maxk = maxd * maxs; var fi,fo: text; i,t: integer; n,m: qword; free: array[1..maxk] of boolean; list: array[1..maxk] of integer; nlist: integer; d: array[1..maxd] of integer; F: array[-1..9,1..maxd,0..maxk] of qword; procedure openfile; begin assign(fi, input); reset(fi); assign(fo, output); rewrite(fo); end; procedure genshappy; var i,ss,k,tmp: integer; begin fillchar(free, sizeof(free), true); free[4] := false; for i := 1 to maxk do if free[i] then begin ss := i; repeat k := ss; ss := 0; while k <> 0 do begin tmp := k mod 10; ss := ss + sqr(tmp); k := k div 10; end; if ss = 1 then break; if not free[ss] then begin free[i] := false; break; end; until false; end; nlist := 0; for i := 1 to maxk do if free[i] then begin inc(nlist); list[nlist] := i; end; end; procedure gensnum; var i,j,k,fs: integer; begin fillchar(F, sizeof(F), 0); for i := 0 to 9 do F[i,1,i * i] := 1; for j := 2 to maxd do for i := 0 to 9 do for k := sqr(i) to j * maxs do for fs := 0 to 9 do F[i,j,k] := F[i,j,k] + F[fs,j - 1,k - sqr(i)]; end; function calc(k,c: integer): qword; var i,j,s: integer; tmp: qword; begin if k = 0 then exit(0); s := d[k]; if k > 1 then dec(s); tmp := 0; for i := 0 to s do for j := 1 to nlist do if list[j] >= c then tmp := tmp + F[i,k,list[j] - c]; calc := tmp + calc(k - 1,c + sqr(d[k])); end; procedure solve; var k,i,j,delta,digit: integer; count,curr,next: qword; begin readln(fi, n, m); fillchar(d, sizeof(d), 0); k := 0; while n > 0 do begin inc(k); d[k] := n mod 10; n := n div 10; end; m := m + calc(k,0); delta := 0; j := 0; count := 0; while count < m do begin inc(j); for i := 1 to 9 do for k := 1 to nlist do count := count + F[i,j,list[k]]; end; k := j; fillchar(d, sizeof(d), 0); for j := k downto 1 do begin digit := 0; curr := 0; next := 0; while next < m do begin curr := next; for k := 1 to nlist do if list[k] >= delta then next := next + F[digit,j,list[k] - delta]; inc(digit); end; m := m - curr; dec(digit); d[j] := digit; delta := delta + sqr(digit); end; end; procedure printresult; var i,k: integer; begin k := maxd; while d[k] = 0 do dec(k); for i := k downto 1 do write(fo, d[i]); writeln(fo); end; procedure closefile; begin close(fo); close(fi); end; begin openfile; genshappy; gensnum; readln(fi, t); for i := 1 to t do begin solve; printresult; end; closefile; end.
Code mẫu của khuc_tuan
#include <iostream> using namespace std; bool mark[2000]; int c[20], nc; long long result; long long F[17][2][1500]; int sum2(int x) { if(x < 10) return x * x; else return (x % 10) * (x % 10) + sum2(x / 10); } long long go(int pos, bool isgreater, int total, long long cur, long long m) { if(m <= 0) return 0; if(pos == -1) { if(mark[total] && isgreater) { if(m == 1) result = cur; return 1; } return 0; } long long &ret = F[pos][isgreater][total], tmp; if(ret != -1 && ret < m) return ret; ret = 0; for(int ad=0;ad<10;++ad) if(isgreater || ad >= c[pos]) { tmp = go( pos - 1, isgreater || ad > c[pos], total + ad * ad, cur * 10 + ad, m); m -= tmp; ret += tmp; } return ret; } int main() { for(int i=1;i<2000;++i) { int x = i; for(int k=0;k<1000;++k) x = sum2(x); mark[i] = (x == 1); } int st; long long n, m; cin >> st; for(int k=0;k<st;++k) { cin >> n >> m; memset( c, 0, sizeof(c)); for(nc = 0; n > 0; n /= 10) c[nc++] = n % 10; memset( F, -1, sizeof(F)); go(16, 0, 0, 0, m); cout << result << endl; } return 0; }
Bình luận