← 返回题目列表

Codeforces · 507/C

C. 猜猜你的出路!

中文机器翻译题面 查看原题

Amr 购买了一款新视频游戏“猜猜你的出路!”。游戏的目标是找到迷宫的出口,该出口看起来像高度为 h 的完美二叉树。玩家最初站在树的根部,树的出口位于某个叶节点。

让我们从左到右索引 1 到 2h 的所有叶节点。出口位于某个节点 n,其中 1 ≤ n ≤ 2h,玩家不知道出口在哪里,所以他必须猜测出路!

Amr遵循简单的算法来选择路径。让我们考虑无限命令字符串“LRLRLRLRL...”(由交替的字符“L”和“R”组成)。 Amr 使用以下规则顺序执行字符串的字符:

- 字符“L”表示“转到当前节点的左子节点”;
- 字符“R”表示“转到当前节点的右子节点”;
- 如果目标节点已经被访问过,Amr 跳过当前命令,否则移动到目标节点;
- 如果Amr连续跳过两个命令,他会在执行下一个命令之前返回当前节点的父节点;
- 如果到达不是出口的叶子节点,则返回当前节点的父节点;
- 如果他到达出口,游戏就结束。

现在 Amr 想知道,如果他遵循这个算法,在到达出口之前他将访问多少个节点?

输入

输入由两个整数 h、n (1 ≤ h ≤ 50, 1 ≤ n ≤ 2h) 组成。

输出

按照此算法输出一个整数,表示 Amr 在到达出口之前将要访问的节点数(不包括出口节点)。

示例

输入 #1

1 2

输出 #1

2

输入 #2

2 3

输出 #2

5

输入 #3

3 6

输出 #3

10

输入#4

10 1024

输出#4

2046

注意

高度为 h 的完美二叉树是由 h + 1 层组成的二叉树。级别 0 由称为根的单个节点组成,级别 h 由称为叶的 2h 个节点组成。每个不是叶子的节点都恰好有两个子节点,左节点和右节点。

下图是示例测试编号 3。节点按照访问顺序进行标记。