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.

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

Please read the guidelines before commenting.


There are no comments at the moment.