Hướng dẫn giải của TAPN
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
const maxn=31; var n,t,i:longint; re,m:int64; d:array[1..31] of longint; c,a:array[0..31,-1..31] of int64; procedure init; var i,j:longint; begin fillchar(a,sizeof(a),0); for i:=1 to maxn do begin a[i,0]:=1; a[i,i]:=1; end; for i:=2 to maxn do for j:=1 to i-1 do a[i,j]:=a[i-1,j]+a[i-1,j-1]; fillchar(c,sizeof(c),0); for i:=1 to maxn do begin c[i,0]:=1; for j:=1 to i do c[i,j]:=c[i,j-1]+a[i,j]; end; end; procedure find; var i,pos,j:longint; begin fillchar(d,sizeof(d),0); pos:=0; if m=1 then exit; if m=c[n,n] then begin for i:=1 to n do d[i]:=1; exit; end; for i:=0 to n-1 do if m>c[n,i] then pos:=i else break; m:=c[n,pos+1]-m+1; inc(pos); for i:=n-1 downto 1 do begin if m>a[i,pos] then begin d[n-i]:=1; m:=m-a[i,pos]; dec(pos); end else d[n-i]:=0; end; d[n]:=pos; end; begin init; repeat readln(n,m); find; re:=1; for i:=1 to n do if d[i]=0 then re:=re*2+1 else re:=re*3+1; writeln(re); until eof; end.
Code mẫu của RR
//Written by RR #include <cstdio> #include <cstdlib> #include <algorithm> #include <iostream> #define MAXN 32 #define FOR(i,a,b) for(typeof(a) i=a; i<=b; i++) #define FORD(i,a,b) for(typeof(a) i=a; i>=b; i--) using namespace std; long n,bit[MAXN]; long long m,res,c[MAXN][MAXN]; void init() { c[0][0]=1; FOR(i,1,MAXN-1) { c[i][0]=1; FOR(j,1,MAXN-1) c[i][j]=c[i-1][j]+c[i-1][j-1]; } } void solve() { long k=0; while (c[n][k]<m) { m-=c[n][k]; k++; } m=c[n][k]-m+1; long len=n; FOR(i,1,n) { if (c[len-1][k]>=m) bit[i]=0; else {m-=c[len-1][k]; bit[i]=1; k--; } len--; } res=1; FOR(i,1,n) if (bit[i]==0) res=res*2+1; else res=res*3+1; cout<<res<<"\n"; } int main() { #ifdef DEBUG freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif init(); while (scanf("%ld %lld",&n,&m)==2) solve(); return 0; }
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> long long KQ(long long a[],long long n) { long long T=1; for(long i=1;i<=n;i++) { if(a[i]==0) T=T*2+1; else T=T*3+1; } return T; } main() { long long C[33][33],a[33],n,m,t; for(long i=0;i<=32;i++) for(long j=0;j<=32;j++) C[i][j]=0; for(long i=0;i<=32;i++) C[0][i]=1; for(long i=1;i<=32;i++) for(long j=0;j<=i;j++) C[j][i]=C[j][i-1]+C[j-1][i-1]; while(scanf("%lld %lld",&n,&m)>0) { for(long i=1;i<=n;i++) a[i]=0; for(long i=0;i<=n;i++) { //printf("%lld ",m); if(m<=C[i][n]) { //printf("0 "); t=i; break; } else m=m-C[i][n]; } //printf("1 "); long u=n-1; for(long i=t;i>=1;i--) { while(1) { if(m<=C[i-1][u]) { a[n-u]=1; u--; break; } else m=m-C[i-1][u]; u--; } } printf("%lld\n",KQ(a,n)); } //getch(); }
Code mẫu của khuc_tuan
#include <cstdio> #include <set> using namespace std; int main() { int n; long long m; long long F[32][32]; memset( F, 0, sizeof(F)); F[0][0] = 1; for(int i=1;i<32;++i) { for(int j=0;j<=i;++j) { F[i][j] = F[i-1][j]; if(j>0) F[i][j] += F[i-1][j-1]; } } while(scanf("%d%lld", &n, &m) != EOF) { long long r = 1; for(int i=0;i<=n;++i) { if(m>F[n][i]) m -= F[n][i]; else { int pos = n; int sl = i; while(pos > 0) { if(sl > 0 && m <= F[pos-1][sl-1]) { r = r * 3 + 1; --sl; --pos; } else { if(sl>0) m -= F[pos-1][sl-1]; r = r * 2 + 1; --pos; } } break; } } printf("%lld\n", r); } return 0; }
Bình luận