codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.