102433: [AtCoder]ABC243 D - Moves on Binary Tree

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

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, and R.
  • 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.

Figure

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$,由ULR组成。
  • 当高桥同学在根顶点时,他不会尝试移动到父顶点。
  • 当高桥同学在叶子顶点时,他不会尝试移动到子顶点。
  • 在$N$次移动后,高桥同学所在的顶点的索引不超过$10^{18}$。

输入

输入以标准输入的以下格式给出:

$N$ $X$
$S$

输出

打印答案。


样例输入 1

3 2
URL

样例输出 1

6

完美的二叉树具有以下结构。

Figure

在三次移动中,高桥同学依次经过$2 \to 1 \to 3 \to 6$。


样例输入 2

4 500000000000000000
RRUU

样例输出 2

500000000000000000

在过程中,高桥同学可能在索引超过$10^{18}$的顶点上。


样例输入 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

样例输出 3

126419752371

加入题单

上一题 下一题 算法标签: