1506B.md (2124B)
1 Source: https://codeforces.com/problemset/problem/1506/B 2 3 B. Partial Replacement 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 are given a number $k$ and a string $s$ of length $n$, consisting of the characters '.' and '*'. You want to replace some of the '*' characters with 'x' characters so that the following conditions are met: 22 23 * The first character '*' in the original string should be replaced with 'x'; 24 * The last character '*' in the original string should be replaced with 'x'; 25 * The distance between two neighboring replaced characters 'x' must not exceed $k$ (more formally, if you replaced characters at positions $i$ and $j$ ($i \lt j$) and at positions $[i+1, j-1]$ there is no "x" symbol, then $j-i$ must be no more than $k$). 26 27 For example, if $n=7$, $s=$.**.*** and $k=3$, then the following strings will satisfy the conditions above: 28 29 * .xx.*xx; 30 * .x*.x*x; 31 * .xx.xxx. 32 33 But, for example, the following strings will not meet the conditions: 34 35 * .**.*xx (the first character '*' should be replaced with 'x'); 36 * .x*.xx* (the last character '*' should be replaced with 'x'); 37 * .x*.*xx (the distance between characters at positions $2$ and $6$ is greater than $k=3$). 38 39 Given $n$, $k$, and $s$, find the minimum number of '*' characters that must be replaced with 'x' in order to meet the above conditions. 40 41 Input 42 43 The first line contains one integer $t$ ($1 \le t \le 500$). Then $t$ test cases follow. 44 45 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 50$). 46 47 The second line of each test case contains a string $s$ of length $n$, consisting of the characters '.' and '*'. 48 49 It is guaranteed that there is at least one '*' in the string $s$. 50 51 It is guaranteed that the distance between any two neighboring '*' characters does not exceed $k$. 52 53 Output 54 55 For each test case output the minimum number of '*' characters that must be replaced with 'x' characters in order to satisfy the conditions above. 56 57 Example 58 59 Input 60 61 ``` 62 5 63 7 3 64 .**.*** 65 5 1 66 ..*.. 67 5 2 68 *.*.* 69 3 2 70 *.* 71 1 1 72 * 73 ``` 74 75 Output 76 77 ``` 78 3 79 1 80 3 81 2 82 1 83 ```