Codeforces Round 963 (Div. 2) |
---|
Finished |
This is the easy version of the problem. The only difference is that in this version $$$k \le n$$$. You can make hacks only if both versions of the problem are solved.
Given a $$$w \times h$$$ rectangle on the $$$Oxy$$$ plane, with points $$$(0, 0)$$$ at the bottom-left and $$$(w, h)$$$ at the top-right of the rectangle.
You also have a robot initially at point $$$(0, 0)$$$ and a script $$$s$$$ of $$$n$$$ characters. Each character is either L, R, U, or D, which tells the robot to move left, right, up, or down respectively.
The robot can only move inside the rectangle; otherwise, it will change the script $$$s$$$ as follows:
Then, it will execute the changed script starting from the character which it couldn't execute.
The script $$$s$$$ will be executed for $$$k$$$ times continuously. All changes to the string $$$s$$$ will be retained even when it is repeated. During this process, how many times will the robot move to the point $$$(0, 0)$$$ in total? Note that the initial position does NOT count.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains four integers $$$n$$$, $$$k$$$, $$$w$$$, and $$$h$$$ ($$$1 \le n, w, h \le 10^6$$$; $$$1 \le k \le n$$$).
The second line contains a single string $$$s$$$ of size $$$n$$$ ($$$s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\}$$$) — the script to be executed.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print a single integer — the number of times the robot reaches $$$(0, 0)$$$ when executing script $$$s$$$ for $$$k$$$ times continuously.
52 2 2 2UR4 2 1 1LLDD6 3 3 1RLRRRL5 5 3 3RUURD7 5 3 4RRDLUUU
0 4 3 0 1
In the first test case, the robot only moves up and right. In the end, it occupies the position $$$(2, 2)$$$ but never visits $$$(0, 0)$$$. So the answer is $$$0$$$.
In the second test case, each time executing the script the robot visits the origin twice. And since $$$k=2$$$, it visits the origin $$$2 \cdot 2 = 4$$$ times overall.
In the third test case, the visualization is shown as below:
Name |
---|