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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.