← 返回题目列表

Codeforces · 1993/F1

F1. Dyn脚本机器人(简单版)

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

这是问题的简单版本。唯一的区别是在这个版本中 $$$k \le n$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

给定 $$$Oxy$$$ 平面上的 $$$w \times h$$$ 矩形,点 $$$(0, 0)$$$ 位于矩形的左下角,$$$(w, h)$$$ 位于矩形的右上角。

您还有一个最初位于 $$$(0, 0)$$$ 点的机器人和一个包含 $$$n$$$ 个字符的脚本 $$$s$$$。每个字符都是 L、R、U 或 D,分别告诉机器人向左、向右、向上或向下移动。

机器人只能在矩形内移动;否则,它将更改脚本$$$s$$$,如下所示:

- 如果它尝试移出垂直边界,则会将所有 L 字符更改为 R 字符(反之亦然,所有 R 字符更改为 L 字符)。
- 如果它尝试移出水平边界,则会将所有 U 字符更改为 D(反之亦然,将所有 D 更改为 U)。

然后,它将从无法执行的字符开始执行更改后的脚本。

机器人运动过程示例,$$$s = \texttt{"ULULURD"}$$$

脚本$$$s$$$将连续执行$$$k$$$次。即使重复,对字符串 $$$s$$$ 的所有更改也将被保留。在这个过程中,机器人总共会移动到$$$(0, 0)$$$点多少次?请注意,初始位置不计算在内。

输入

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

每个测试用例的第一行包含四个整数 $$$n$$$、$$$k$$$、$$$w$$$ 和 $$$h$$$ ($$$1 \le n, w, h \le 10^6$$$; $$$1 \le k \le n$$$)。

第二行包含一个大小为 $$$n$$$ 的字符串 $$$s$$$ ($$$s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\}$$$) — 要执行的脚本。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,打印一个整数 - 当连续执行 $$$s$$$ 脚本 $$$k$$$ 次时,机器人到达 $$$(0, 0)$$$ 的次数。

示例

输入 #1

5
2 2 2 2
UR
4 2 1 1
LLDD
6 3 3 1
RLRRRL
5 5 3 3
RUURD
7 5 3 4
RRDLUUU

输出 #1

0
4
3
0
1

注意

在第一个测试用例中,机器人仅向上和向右移动。最后,它占据了位置$$$(2, 2)$$$,但从未访问过$$$(0, 0)$$$。所以答案是$$$0$$$。

在第二个测试用例中,每次执行脚本时,机器人都会访问原点两次。由于 $$$k=2$$$,它总共访问原点 $$$2 \cdot 2 = 4$$$ 次。

在第三个测试用例中,可视化如下所示: