codeforces-scrape

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

1324C.md (2923B)


      1 Source: https://codeforces.com/problemset/problem/1324/C
      2 
      3 C. Frog Jumps
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 There is a frog staying to the left of the string $s = s_1 s_2 \ldots s_n$ consisting of $n$ characters (to be more precise, the frog initially stays at the cell $0$). Each character of $s$ is either 'L' or 'R'. It means that if the frog is staying at the $i$-th cell and the $i$-th character is 'L', the frog can jump only to the left. If the frog is staying at the $i$-th cell and the $i$-th character is 'R', the frog can jump only to the right. The frog can jump only to the right from the cell $0$.
     22 
     23 Note that the frog can jump into the same cell twice and can perform as many jumps as it needs.
     24 
     25 The frog wants to reach the $n+1$-th cell. The frog chooses some positive integer value $d$ before the first jump (and cannot change it later) and jumps by no more than $d$ cells at once. I.e. if the $i$-th character is 'L' then the frog can jump to any cell in a range $[max(0, i - d); i - 1]$, and if the $i$-th character is 'R' then the frog can jump to any cell in a range $[i + 1; min(n + 1; i + d)]$.
     26 
     27 The frog doesn't want to jump far, so your task is to find the minimum possible value of $d$ such that the frog can reach the cell $n+1$ from the cell $0$ if it can jump by no more than $d$ cells at once. It is guaranteed that it is always possible to reach $n+1$ from $0$.
     28 
     29 You have to answer $t$ independent test cases.
     30 
     31 Input
     32 
     33 The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 The next $t$ lines describe test cases. The $i$-th test case is described as a string $s$ consisting of at least $1$ and at most $2 \cdot 10^5$ characters 'L' and 'R'.
     36 
     37 It is guaranteed that the sum of lengths of strings over all test cases does not exceed $2 \cdot 10^5$ ($\sum |s| \le 2 \cdot 10^5$).
     38 
     39 Output
     40 
     41 For each test case, print the answer — the minimum possible value of $d$ such that the frog can reach the cell $n+1$ from the cell $0$ if it jumps by no more than $d$ at once.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 6
     49 LRLRRLL
     50 L
     51 LLR
     52 RRRR
     53 LLLLLL
     54 R
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 3
     61 2
     62 3
     63 1
     64 7
     65 1
     66 ```
     67 
     68 Note
     69 
     70 The picture describing the first test case of the example and one of the possible answers:
     71 
     72 ![](https://espresso.codeforces.com/3792fcac8b01d493591a870c91a14e62d2bb3961.png)
     73 
     74 In the second test case of the example, the frog can only jump directly from $0$ to $n+1$.
     75 
     76 In the third test case of the example, the frog can choose $d=3$, jump to the cell $3$ from the cell $0$ and then to the cell $4$ from the cell $3$.
     77 
     78 In the fourth test case of the example, the frog can choose $d=1$ and jump $5$ times to the right.
     79 
     80 In the fifth test case of the example, the frog can only jump directly from $0$ to $n+1$.
     81 
     82 In the sixth test case of the example, the frog can choose $d=1$ and jump $2$ times to the right.