D - N阶汉诺塔变形

朱雀 2021-03-28 13:52 461阅读 0赞

## 题目描述 ##

相信大家都知道汉诺塔问题。那么现在对汉诺塔问题做一些限制，成为一个新的玩法。

在一个底座上，从左到右有三个分别命名为A、B和C的塔座，有n个大小不一的圆盘。这些圆盘一开始，从小到大按顺序叠加在塔座A上，形成一座上小下大的塔，塔座B和C为空。我们将n个圆盘，从小到大编号为1~n。现要求将塔座A上的n个圆盘移至塔座C上并仍按照同样的顺序叠排，圆盘移动时必须遵循以下规则：  
（1）每次只能将一个圆盘从一个塔座移动到相邻的塔座上  
（2）所有圆盘可以叠在A、B和C中的任一塔座上

（3）任何时刻都不能将一个较大的圆盘压在较小的圆盘上面

那么问题来了，对于一个n阶（阶数即是问题中圆盘的个数）的上述问题，用最少操作次数将圆盘塔从塔座A移动到塔座C的操作总是固定的。请问，n阶问题执行k步操作后，塔座A、B和C上圆盘的情况是怎样的？从大到小输出三个塔座上的圆盘的编号（如果该塔座上没有圆盘，请输出0）。

比如，塔座A上有圆盘1，3；塔座B上有圆盘2；塔座C上有圆盘4。我们将输出：

3 1

## 输入描述: ##

数据有多组，处理到文件结束。
每组数据一行输入，有两个整数n和k，n代表问题的阶数，k代表执行的步数。

## 输出描述: ##

每组数据输出占三行。
第一行描述塔座A的情况。
第二行描述塔座B的情况。
第三行描述塔座C的情况。

示例1

## 输入 ##

3 5
    4 10

## 输出 ##

3 1
    2
    0
    4
    3 1
    2

## 备注: ##

10000组数据。
    对于100%的数据，
    1 <= n < 40;
    1 <= k < (3^n)。

## 题解 ##

规律。

手动模拟一下$3$的时候，可以发现每个数字所在位置是存在规律的。

数字$1$的位置规律：123 321 123 321

数字$2$的位置规律：111222333 333222111 111222333 333222111

......

#include<bits/stdc++.h>
    using namespace std;
    
    int n;
    long long k;
    long long b[50];
    vector<int> g[5];
    
    int main() {
      b[0] = 1LL;
      for(int i = 1; i < 40; i ++) {
        b[i] = b[i - 1] * 3LL;
      }
      while(~scanf("%d%lld", &n, &k)) {
        g[1].clear();
        g[2].clear();
        g[3].clear();
        for(int i = n; i >= 1; i --) {
          long long p = k % (b[i] * 2LL);
          p = p / b[i - 1];
          if(p <= 2) {}
          else p = 5 - p;
          p ++;
          g[p].push_back(i);
        }
        for(int i = 1; i <= 3; i ++) {
          if(g[i].size() == 0) printf("0\n");
          else {
            for(int j = 0; j < g[i].size(); j ++) {
              printf("%d", g[i][j]);
              if(j < g[i].size() - 1) printf(" ");
              else printf("\n");
            }
          }
        }
      }
      return 0;
    }