Editorial for VM 09 Bài 06 - SỐ RÕ RÀNG
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
#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; }
Comments