#G1087. [GESP202412 六级] 树上游走

[GESP202412 六级] 树上游走

[GESP202412 六级] 树上游走

题目描述

小杨有一棵包含无穷节点的二叉树(即每个节点都有左儿子节点和右儿子节点;除根节点外,每个节点都有父节点),其中根节点的编号为 11,对于节点 ii,其左儿子的编号为 2×i2 \times i,右儿子的编号为 2×i+12 \times i + 1。

小杨会从节点 ss 开始在二叉树上移动,每次移动为以下三种移动方式的任意一种:

  • 第 1 种移动方式:如果当前节点存在父亲节点,向上移动到当前节点的父亲节点,否则不移动;
  • 第 2 种移动方式:移动到当前节点的左儿子;
  • 第 3 种移动方式:移动到当前节点的右儿子。

小杨想知道移动 nn 次后自己所处的节点编号。数据保证最后的所处的节点编号不超过 101210^{12}。

输入格式

第一行包含两个正整数 n,sn, s,代表移动次数和初始节点编号。

第二行包含一个长度为 nn 且仅包含大写字母 U, L, R 的字符串,代表每次移动的方式,其中 U 代表第 1 种移动方式,L 代表第 2 种移动方式,R 代表第 3 种移动方式。

输出格式

输出一个正整数,代表最后所处的节点编号。

样例 #1

样例输入 #1

3 2
URR

样例输出 #1

7

样例解释

小杨的移动路线为 2−1−3−72-1-3-7。

数据范围

子任务编号 数据点占比 nn ss
1 20% ≤10≤ 10 ≤2≤ 2
2 ≤50≤ 50 ≤10≤ 10
3 60% ≤106≤ 10^6 ≤1012≤ 10^{12}
  • 对于全部数据,保证有 1≤n≤1061 ≤ n ≤ 10^6,1≤s≤10121 ≤ s ≤ 10^{12}。