codeforces-scrape

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

1744C.md (2969B)


      1 Source: https://codeforces.com/problemset/problem/1744/C
      2 
      3 C. Traffic Light
      4 
      5 time limit per test
      6 
      7 1 second
      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 You find yourself on an unusual crossroad with a weird traffic light. That traffic light has three possible colors: red (r), yellow (y), green (g). It is known that the traffic light repeats its colors every $n$ seconds and at the $i$-th second the color $s_i$ is on.
     22 
     23 That way, the order of the colors is described by a string. For example, if $s=$"rggry", then the traffic light works as the following: red-green-green-red-yellow-red-green-green-red-yellow- ... and so on.
     24 
     25 More formally, you are given a string $s_1, s_2, \ldots, s_n$ of length $n$. At the first second the color $s_1$ is on, at the second — $s_2$, ..., at the $n$-th second the color $s_n$ is on, at the $n + 1$-st second the color $s_1$ is on and so on.
     26 
     27 You need to cross the road and that can only be done when the green color is on.
     28 
     29 You know which color is on the traffic light at the moment, but you don't know the current moment of time. You need to find the minimum amount of time in which you are guaranteed to cross the road.
     30 
     31 You can assume that you cross the road immediately.
     32 
     33 For example, with $s=$"rggry" and the current color r there are two options: either the green color will be on after $1$ second, or after $3$. That way, the answer is equal to $3$ — that is the number of seconds that we are guaranteed to cross the road, if the current color is r.
     34 
     35 Input
     36 
     37 The first line contains a single integer $t$ $(1 \leq t \leq 10^4$) — the number of test cases.
     38 
     39 Then the description of the test cases follows.
     40 
     41 The first line of each test case contains an integer $n$ and a symbol $c$ ($1 \leq n \leq 2 \cdot 10^5$, $c$ is one of allowed traffic light colors r, y or g)— the length of the string $s$ and the current color of the traffic light.
     42 
     43 The second line of each test case contains a string $s$ of the length $n$, consisting of the letters r, y and g.
     44 
     45 It is guaranteed that the symbol g is in the string $s$ and the symbol $c$ is in the string $s$.
     46 
     47 It is guaranteed, that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.
     48 
     49 Output
     50 
     51 For each test case output the minimal number of second in which you are guaranteed to cross the road.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 6
     59 
     60 5 r
     61 
     62 rggry
     63 
     64 1 g
     65 
     66 g
     67 
     68 3 r
     69 
     70 rrg
     71 
     72 5 y
     73 
     74 yrrgy
     75 
     76 7 r
     77 
     78 rgrgyrg
     79 
     80 9 y
     81 
     82 rrrgyyygy
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 3
     89 0
     90 2
     91 4
     92 1
     93 4
     94 ```
     95 
     96 Note
     97 
     98 The first test case is explained in the statement.
     99 
    100 In the second test case the green color is on so you can cross the road immediately.
    101 
    102 In the third test case, if the red color was on at the second second, then we would wait for the green color for one second, and if the red light was on at the first second, then we would wait for the green light for two seconds.
    103 
    104 In the fourth test case the longest we would wait for the green color is if we wait for it starting from the fifth second.