2070B.md (2810B)
1 Source: https://codeforces.com/problemset/problem/2070/B 2 3 B. Robot Program 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There is a robot on the coordinate line. Initially, the robot is located at the point $x$ ($x \ne 0$). The robot has a sequence of commands of length $n$ consisting of characters, where L represents a move to the left by one unit (from point $p$ to point $(p-1)$) and R represents a move to the right by one unit (from point $p$ to point $(p+1)$). 22 23 The robot starts executing this sequence of commands (one command per second, in the order they are presented). However, whenever the robot reaches the point $0$, the counter of executed commands is reset (i. e. it starts executing the entire sequence of commands from the very beginning). If the robot has completed all commands and is not at $0$, it stops. 24 25 Your task is to calculate how many times the robot will enter the point $0$ during the next $k$ seconds. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 The first line of a test case contains three integers $n$, $x$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $-n \le x \le n$; $n \le k \le 10^{18}$). 32 33 The second line of a test case contains a string $s$ consisting of $n$ characters L and/or R. 34 35 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, print a single integer — the number of times the robot will enter the point $0$ during the next $k$ seconds. 40 41 Example 42 43 Input 44 45 ``` 46 6 47 48 3 2 6 49 50 LLR 51 52 2 -1 8 53 54 RL 55 56 4 -2 5 57 58 LRRR 59 60 5 3 7 61 62 LRRLL 63 64 1 1 1 65 66 L 67 68 3 -1 4846549234412827 69 70 RLR 71 ``` 72 73 Output 74 75 ``` 76 1 77 4 78 1 79 0 80 1 81 2423274617206414 82 ``` 83 84 Note 85 86 In the first example, the robot moves as follows: $2 \rightarrow 1 \rightarrow \underline{0} \rightarrow -1 \rightarrow -2 \rightarrow -1$. The robot has completed all instructions from the sequence and is not at $0$. So it stops after $5$ seconds and the point $0$ is entered once. 87 88 In the second example, the robot moves as follows: $-1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1$. The robot worked $8$ seconds and the point $0$ is entered $4$ times. 89 90 In the third example, the robot moves as follows: $-2 \rightarrow -3 \rightarrow -2 \rightarrow -1 \rightarrow \underline{0} \rightarrow -1$. The robot worked $5$ seconds and the point $0$ is entered once. 91 92 In the fourth example, the robot moves as follows: $3 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 2$. The robot has completed all instructions from the sequence and is not at $0$. So it stops after $5$ seconds, without reaching the point $0$.