codeforces-scrape

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

1690D.md (1779B)


      1 Source: https://codeforces.com/problemset/problem/1690/D
      2 
      3 D. Black and White Stripe
      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 You have a stripe of checkered paper of length $n$. Each cell is either white or black.
     22 
     23 What is the minimum number of cells that must be recolored from white to black in order to have a segment of $k$ consecutive black cells on the stripe?
     24 
     25 If the input data is such that a segment of $k$ consecutive black cells already exists, then print 0.
     26 
     27 Input
     28 
     29 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     30 
     31 Next, descriptions of $t$ test cases follow.
     32 
     33 The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2\cdot10^5$). The second line consists of the letters 'W' (white) and 'B' (black). The line length is $n$.
     34 
     35 It is guaranteed that the sum of values $n$ does not exceed $2\cdot10^5$.
     36 
     37 Output
     38 
     39 For each of $t$ test cases print an integer — the minimum number of cells that need to be repainted from white to black in order to have a segment of $k$ consecutive black cells.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 
     48 5 3
     49 
     50 BBWBW
     51 
     52 5 5
     53 
     54 BBWBW
     55 
     56 5 1
     57 
     58 BBWBW
     59 
     60 1 1
     61 
     62 W
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 1
     69 2
     70 0
     71 1
     72 ```
     73 
     74 Note
     75 
     76 In the first test case, $s$="BBWBW" and $k=3$. It is enough to recolor $s_3$ and get $s$="BBBBW". This string contains a segment of length $k=3$ consisting of the letters 'B'.
     77 
     78 In the second test case of the example $s$="BBWBW" and $k=5$. It is enough to recolor $s_3$ and $s_5$ and get $s$="BBBBB". This string contains a segment of length $k=5$ consisting of the letters 'B'.
     79 
     80 In the third test case of the example $s$="BBWBW" and $k=1$. The string $s$ already contains a segment of length $k=1$ consisting of the letters 'B'.