AT_abc115_d [ABC115D] Christmas

题目描述

在某个世界里，今天是圣诞节。

在高羽先生的派对上，他决定制作多维汉堡。等级 $L$ 汉堡（$L$ 是大于等于 $0$ 的整数）定义如下：

• 等级 $0$ 汉堡就是 $1$ 层肉饼。
• 等级 $L$ 汉堡（$L \geq 1$）是从下往上依次叠加：$1$ 层面包、$1$ 个等级 $L-1$ 汉堡、$1$ 层肉饼、$1$ 个等级 $L-1$ 汉堡、$1$ 层面包。

例如，用 P 表示肉饼，用 B 表示面包，则等级 $1$ 汉堡为 BPPPB（旋转 $90$ 度后），等级 $2$ 汉堡为 BBPBPBPBB。

高羽先生制作的是等级 $N$ 的汉堡。腊肠犬“ルンルン”会从这个汉堡的最下方吃掉 $X$ 层（每一层可以是肉饼或面包）。请问ルンルン会吃到多少块肉饼？

输入格式

输入由标准输入给出，格式如下：

$N$ $X$

输出格式

输出等级 $N$ 汉堡从下往上数 $X$ 层中包含的肉饼数量。

样例 1

输入

2 7

输出

4

样例 2

输入

1 1

输出

0

样例 3

输入

50 4321098765432109

输出

2160549382716056

说明/提示

限制条件

• $1 \leq N \leq 50$
• $1 \leq X \leq$（等级 $N$ 汉堡的总层数）
• $N, X$ 均为整数。

样例解释 1

等级 $2$ 汉堡（BBPBPBPBB）的最下方 $7$ 层中包含 $4$ 块肉饼。

样例解释 2

等级 $1$ 汉堡的最底层是面包。

样例解释 3

等级 $50$ 汉堡的层数已经大到无法用 $32$ 位整数表示。

由 ChatGPT 4.1 翻译