Editorial for TAPN
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
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; }
Comments