codeforces-scrape

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

1992D.md (3515B)


      1 Source: https://codeforces.com/problemset/problem/1992/D
      2 
      3 D. Test of Love
      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 ErnKor is ready to do anything for Julen, even to swim through crocodile-infested swamps. We decided to test this love. ErnKor will have to swim across a river with a width of $1$ meter and a length of $n$ meters.
     22 
     23 The river is very cold. Therefore, in total (that is, throughout the entire swim from $0$ to $n+1$) ErnKor can swim in the water for no more than $k$ meters. For the sake of humanity, we have added not only crocodiles to the river, but also logs on which he can jump. Our test is as follows:
     24 
     25 Initially, ErnKor is on the left bank and needs to reach the right bank. They are located at the $0$ and $n+1$ meters respectively. The river can be represented as $n$ segments, each with a length of $1$ meter. Each segment contains either a log 'L', a crocodile 'C', or just water 'W'. ErnKor can move as follows:
     26 
     27 * If he is on the surface (i.e., on the bank or on a log), he can jump forward for no more than $m$ ($1 \le m \le 10$) meters (he can jump on the bank, on a log, or in the water).
     28 * If he is in the water, he can only swim to the next river segment (or to the bank if he is at the $n$-th meter).
     29 * ErnKor cannot land in a segment with a crocodile in any way.
     30 
     31 Determine if ErnKor can reach the right bank.
     32 
     33 Input
     34 
     35 The first line contains a single integer $t$ ($1 \le t \le 10^4$)  — the number of test cases.
     36 
     37 The first line of each test case contains three numbers $n, m, k$ ($0 \le k \le 2 \cdot 10^5$, $1 \le n \le 2 \cdot 10^5$, $1 \le m \le 10$) — the length of the river, the distance ErnKor can jump, and the number of meters ErnKor can swim without freezing.
     38 
     39 The second line of each test case contains a string $a$ of length $n$. $a_i$ denotes the object located at the $i$-th meter. ($a_i \in \{$'W','C','L'$\}$)
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output "YES" if ErnKor can pass the test, and output "NO" otherwise.
     46 
     47 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 6
     55 
     56 6 2 0
     57 
     58 LWLLLW
     59 
     60 6 1 1
     61 
     62 LWLLLL
     63 
     64 6 1 1
     65 
     66 LWLLWL
     67 
     68 6 2 15
     69 
     70 LWLLCC
     71 
     72 6 10 0
     73 
     74 CCCCCC
     75 
     76 6 6 1
     77 
     78 WCCCCW
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 YES
     85 YES
     86 NO
     87 NO
     88 YES
     89 YES
     90 ```
     91 
     92 Note
     93 
     94 Let's consider examples:
     95 
     96 * First example: We jump from the shore to the first log ($0 \rightarrow 1$), from the first log to the second ($1 \rightarrow 3$), from the second to the fourth ($3 \rightarrow 5$), and from the last log to the shore ($5 \rightarrow 7$). So, we have $0 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 7$. Since we did not encounter a crocodile and swam no more than k meters, the answer is «YES».
     97 * Second example: $0 \rightarrow 1$, we jump into the water from the first log ($1 \rightarrow 2$), swim a cell to the log ($2 \leadsto 3$), $3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7$. Since we did not encounter a crocodile and swam no more than k meters, the answer is «YES».
     98 * In the third example, ErnKor needs to swim two cells 'W', but can only swim one. Therefore, the answer is «NO».
     99 * Sixth example: We jump from the shore into the water ($0 \rightarrow 6$) and swim one cell in the water ($6 \leadsto 7$). Since we did not encounter a crocodile and swam no more than k meters, the answer is «YES».