codeforces-scrape

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

2034B.md (2362B)


      1 Source: https://codeforces.com/problemset/problem/2034/B
      2 
      3 B. Rakhsh's Revival
      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 [Rostam](https://en.wikipedia.org/wiki/Rostam)'s loyal horse, [Rakhsh](https://en.wikipedia.org/wiki/Rakhsh), has seen better days. Once powerful and fast, Rakhsh has grown weaker over time, struggling to even move. Rostam worries that if too many parts of Rakhsh's body lose strength at once, Rakhsh might stop entirely. To keep his companion going, Rostam decides to strengthen Rakhsh, bit by bit, so no part of his body is too frail for too long.
     22 
     23  ![](https://espresso.codeforces.com/ace389a4376151924b6a103ba086e314fbadc855.webp) 
     24 
     25 Imagine Rakhsh's body as a line of spots represented by a binary string $s$ of length $n$, where each $0$ means a weak spot and each $1$ means a strong one. Rostam's goal is to make sure that no interval of $m$ consecutive spots is entirely weak (all $0$s).
     26 
     27 Luckily, Rostam has a special ability called Timar, inherited from his mother [Rudabeh](https://en.wikipedia.org/wiki/Rudaba) at birth. With Timar, he can select any segment of length $k$ and instantly strengthen all of it (changing every character in that segment to $1$). The challenge is to figure out the minimum number of times Rostam needs to use Timar to keep Rakhsh moving, ensuring there are no consecutive entirely weak spots of length $m$.
     28 
     29 Input
     30 
     31 The first line contains an integer $t$ ($1 \le t \le 10^4$), the number of test cases.
     32 
     33 The first line of each test case contains three numbers $n$, $m$, $k$ ($1 \le m, k \le n \le 2 \cdot 10^5$). The second line of each test case contains a binary string $s$ of $n$ characters $s_1s_2 \ldots s_n$. ($s_i \in \{$0,1$\}$ for $1 \le i \le n$).
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, output the minimum number of times Rostam needs to use Timar to keep Rakhsh moving, ensuring there are no consecutive entirely weak spots of length $m$.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 3
     47 
     48 5 1 1
     49 
     50 10101
     51 
     52 5 2 1
     53 
     54 10101
     55 
     56 6 3 2
     57 
     58 000000
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 2
     65 0
     66 1
     67 ```
     68 
     69 Note
     70 
     71 In the first test case, we should apply an operation on each 0.
     72 
     73 In the second test case, $s$ is already ok.
     74 
     75 In the third test case, we can perform an operation on interval $[3,4]$ to get 001100.