1970: [USACO 2022 December Contest Bronze] Problem 2. Feeding the Cows

Since all the cows are hungry, FJ decides to plant grassy patches on some of the positions $1\dots N$. Guernseys and Holsteins prefer different types of grass, so if Farmer John decides to plant grass at some location, he must choose to planting either Guernsey-preferred grass or Holstein-preferred grass --- he cannot plant both at the same location. Each patch of grass planted can feed an unlimited number of cows of the appropriate breed.

Each cow is willing to move a maximum of $K$ (0$$≤K≤N−1) positions to reach a patch. Find the minimum number of patches needed to feed all the cows. Also, print a configuration of patches that uses the minimum amount of patches needed to feed the cows. Any configuration that satisfies the above conditions will be considered correct.

Each test case starts with a line containing $N$ and $K$. The next line will contain a string of length $N$, where each character denotes the breed of the i$i$th cow (G meaning Guernsey and H meaning Holstein).

6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH

5
GHHGG
3
.GH.G
2
..GH.
2
...GH
2
...HG
2
HG