← 返回题目列表

Codeforces · 2070/B

B. 机器人程序

中文机器翻译题面 查看原题

坐标线上有一个机器人。最初,机器人位于点 $$$x$$$ ($$$x \ne 0$$$)。机器人有一个长度为 $$$n$$$ 的命令序列,由字符组成,其中 L 表示向左移动一个单位(从点 $$$p$$$ 到点 $$$(p-1)$$$)并且 R 表示向右移动一个单位(从点 $$$p$$$ 到点 $$$(p+1)$$$)。

机器人开始执行这一系列命令(每秒一个命令,按照它们出现的顺序)。然而,每当机器人到达 $$$0$$$ 点时,已执行命令的计数器就会重置(即它从头开始执行整个命令序列)。如果机器人已完成所有命令且不在 $$$0$$$ 处,则它将停止。

你的任务是计算机器人在接下来的$$$k$$$秒内将进入点$$$0$$$多少次。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

测试用例的第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$-n \le x \le n$$$; $$$n \le k \le 10^{18}$$$)。

测试用例的第二行包含一个由 $$$n$$$ 字符组成的字符串 $$$s$$$ L 和/或 R.

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 机器人在接下来的 $$$k$$$ 秒内进入点 $$$0$$$ 的次数。

示例

输入
复制

6
3 2 6
LLR
2 -1 8
RL
4 -2 5
LRRR
5 3 7
LRRLL
1 1 1
L
3 -1 4846549234412827
RLR

输出
复制

1
4
1
0
1
2423274617206414

注意

在第一个示例中,机器人移动如下:$$$2 \rightarrow 1 \rightarrow \underline{0} \rightarrow -1 \rightarrow -2 \rightarrow -1$$$。机器人已完成序列中的所有指令,并且不在 $$$0$$$ 处。因此它会在 $$$5$$$ 秒后停止,并且输入一次 $$$0$$$ 点。

在第二个示例中,机器人移动如下:$$$-1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1$$$。机器人工作 $$$8$$$ 秒,点 $$$0$$$ 输入 $$$4$$$ 次。

在第三个示例中,机器人移动如下:$$$-2 \rightarrow -3 \rightarrow -2 \rightarrow -1 \rightarrow \underline{0} \rightarrow -1$$$。机器人工作 $$$5$$$ 秒,点 $$$0$$$ 输入一次。

在第四个示例中,机器人移动如下:$$$3 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 2$$$。机器人已完成序列中的所有指令,并且不在 $$$0$$$ 处。因此它会在 $$$5$$$ 秒后停止,而不会到达 $$$0$$$ 点。