codeforces-scrape

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

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 ```