#O1005. 汉诺塔的第k步

汉诺塔的第k步

汉诺塔的第 kk 步

题目描述

有 AA、BB、CC 三根柱子,AA 柱上从下到上依次摞着编号为 n,n−1,…,1n, n-1, \ldots, 1 的 nn 个盘子(编号越小盘子越小)。要求把所有盘子按原顺序移动到 CC 柱,移动过程中:

  • 每次只能移动一个盘子,且只能从某根柱子的顶端取走、放到另一根柱子的顶端;
  • 任何时候都不能把大盘子放在小盘子上面。

按最少步数完成移动的方案是唯一的,其移动次数为 2n−12^n - 1。现在给定 nn 和 kk,请求出:

  1. 最少移动次数 m=2n−1m = 2^n - 1;
  2. 第 kk 次移动的是编号为几的盘子(若 k>mk > m,输出 −1-1)。

输入格式

一行两个整数 n,kn, k。

输出格式

一行两个整数,分别为最少移动次数 mm 与第 kk 次移动的盘子编号(或 −1-1),之间用一个空格隔开。

样例 #1

样例输入 #1

3 4

样例输出 #1

7 3

样例说明

n=3n = 3 时的移动顺序为:1,2,1,3,1,2,11, 2, 1, 3, 1, 2, 1,共 77 步。第 44 步移动的是 33 号盘子。

数据规模与约定

数据范围 nn kk
全部测试点 1≤n≤601 \le n \le 60 1≤k≤10181 \le k \le 10^{18}
  • 260−1=11529215046068469752^{60} - 1 = 1152921504606846975,超出 32 位整数范围,请使用 64 位无符号整数。
  • 不需要模拟移动过程,注意观察第 kk 步与 kk 的二进制表示之间的关系。