102433: [AtCoder]ABC243 D - Moves on Binary Tree
Description
Score : $400$ points
Problem Statement
There is a perfect binary tree with $2^{10^{100}}-1$ vertices, numbered $1,2,...,2^{10^{100}}-1$.
Vertex $1$ is the root. For each $1\leq i < 2^{10^{100}-1}$, Vertex $i$ has two children: Vertex $2i$ to the left and Vertex $2i+1$ to the right.
Takahashi starts at Vertex $X$ and performs $N$ moves, represented by a string $S$. The $i$-th move is as follows.
- If the $i$-th character of $S$ is
U, go to the parent of the vertex he is on now. - If the $i$-th character of $S$ is
L, go to the left child of the vertex he is on now. - If the $i$-th character of $S$ is
R, go to the right child of the vertex he is on now.
Find the index of the vertex Takahashi will be on after $N$ moves. In the given cases, it is guaranteed that the answer is at most $10^{18}$.
Constraints
- $1 \leq N \leq 10^6$
- $1 \leq X \leq 10^{18}$
- $N$ and $X$ are integers.
- $S$ has a length of $N$ and consists of
U,L, andR. - When Takahashi is at the root, he never attempts to go to the parent.
- When Takahashi is at a leaf, he never attempts to go to a child.
- The index of the vertex Takahashi is on after $N$ moves is at most $10^{18}$.
Input
Input is given from Standard Input in the following format:
$N$ $X$ $S$
Output
Print the answer.
Sample Input 1
3 2 URL
Sample Output 1
6
The perfect binary tree has the following structure.
In the three moves, Takahashi goes $2 \to 1 \to 3 \to 6$.
Sample Input 2
4 500000000000000000 RRUU
Sample Output 2
500000000000000000
During the process, Takahashi may be at a vertex whose index exceeds $10^{18}$.
Sample Input 3
30 123456789 LRULURLURLULULRURRLRULRRRUURRU
Sample Output 3
126419752371
Input
题意翻译
有一棵 $(2^{10^{100}}-1)$ 个结点的完全二叉树，根结点为 $1$，结点 $i(1\le i < 2^{10^{100}}-1)$ 的左子结点为 $2i$，右子结点为 $2i+1$。 高桥君从结点 $X$ 开始进行 $N$ 次移动，每次移动用一个字符表示： - `U`：移动到当前结点的父结点。 - `L`：移动到当前结点的左子结点。 - `R`：移动到当前结点的右子结点。 移动序列为一个长度为 $N$ 的字符串 $S$。给定 $N,X,S$，求按照 $S$ 依次进行 $N$ 次移动后高桥所处的结点编号。Output
得分：$400$分
问题描述
有一个完美的二叉树，有$2^{10^{100}}-1$个顶点，编号为$1,2,...,2^{10^{100}}-1$。
顶点$1$是根。对于每个$1\leq i < 2^{10^{100}-1}$，顶点$i$有两个子顶点：左侧的顶点$2i$和右侧的顶点$2i+1$。
高桥同学从顶点$X$开始进行$N$次移动，由字符串$S$表示。第$i$次移动如下。
- 如果字符串$S$的第$i$个字符为
U，则移动到他现在所在顶点的父顶点。 - 如果字符串$S$的第$i$个字符为
L，则移动到他现在所在顶点的左子顶点。 - 如果字符串$S$的第$i$个字符为
R，则移动到他现在所在顶点的右子顶点。
在$N$次移动后，找出高桥同学所在的顶点的索引。在给定的案例中，答案保证不超过$10^{18}$。
限制条件
- $1 \leq N \leq 10^6$
- $1 \leq X \leq 10^{18}$
- $N$和$X$为整数。
- $S$的长度为$N$，由
U、L和R组成。 - 当高桥同学在根顶点时，他不会尝试移动到父顶点。
- 当高桥同学在叶子顶点时，他不会尝试移动到子顶点。
- 在$N$次移动后，高桥同学所在的顶点的索引不超过$10^{18}$。
输入
输入以标准输入的以下格式给出：
$N$ $X$ $S$
输出
打印答案。
样例输入 1
3 2 URL
样例输出 1
6
完美的二叉树具有以下结构。
在三次移动中，高桥同学依次经过$2 \to 1 \to 3 \to 6$。
样例输入 2
4 500000000000000000 RRUU
样例输出 2
500000000000000000
在过程中，高桥同学可能在索引超过$10^{18}$的顶点上。
样例输入 3
30 123456789 LRULURLURLULULRURRLRULRRRUURRU
样例输出 3
126419752371