/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
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