题目描述

Dr. X 拿出了一张正方形纸，将其划分成 2 n × 2 n 个大小相等的小格子。纸有正、反两面：初

始时，纸正面朝上。Dr. X 将会按照指定的顺序折叠这张纸，每次折叠，都沿中线将纸对折，

共分四种方向，如图所示：

tle="" align="" />

D (Down)：上半部分向下折，盖在下半部分上。U (Up)：下半部分向上折，盖在上半部分上。

R (Right)：左半部分向右折，盖在右半部分上。

L (Left)：右半部分向左折，盖在左半部分上。

对折时，被翻折的部分会整体翻转 (被翻折的部分正面和反面互换，且原本在最底层的格子折

叠后会翻到最上层)，翻转后的部分作为一个整体，叠加到另一半的上方。经过 2n 次折叠后，

纸最终被折成一个 1 × 1 的方块，由 2 2n 层格子叠成。Dr. X 想知道：初始时位于左上角 (1, 1)

的那个格子，最终在方块中的第几层 (从上往下数，最上面一层为第 1 层)，以及它的正面是朝

上还是朝下。

输入

输出

样例输入

1
DR

样例输出

2 U

样例解释：
初始纸张为 2 × 2。四个格子分别为 (1, 1)、(1, 2)、(2, 1)、(2, 2)，全部正面朝上。
第 1 次 D：上半部分 (1, 1) 和 (1, 2) 向下折，盖在下半部分上。折叠后纸变为 1 × 2 两
层：
左列从上到下：(1, 1) 朝下、(2, 1) 朝上。
右列从上到下：(1, 2) 朝下、(2, 2) 朝上。
第 2 次 R：左列向右折，盖在右列上 (每层翻转)。折叠后纸变为 1 × 1，共 4 层，从上到
下依次为： (2, 1) 朝下、(1, 1) 朝上、(1, 2) 朝下、(2, 2) 朝上。

提示

来源/分类