Problems
N 마리의 소가 일렬로 서있다. 각 소는 젖소(Holstein) 혹은 황소(Guernsey)이다.
젖소와 황소는 각기 다른 종류의 풀을 섭취하는데, 다른 종류의 풀을 같은 위치에 심을 수는 없다.
풀을 한번 심으면 해당 장소에서는 풀이 무한히 자라기에 충분히 많은 수의 소들을 먹일 수 있다.
모든 소는 최대 K만큼만 움직여서 풀을 먹을 수 있다. 풀을 최소한 심어서 모든 소들이 풀을 먹을 수 있게 하고자 한다.
풀을 몇 개 심으면 되고, 어디에 심으면 되는지 출력하는 프로그램을 작성하시오.
Input
첫 번째 줄에 테스트 케이스의 수 T가 입력된다 (1≤T≤10).
두 번째 줄부터 각 테스트 케이스의 첫 번째 줄에 소의 수 N과 소의 최대 이동 범위 K가 입력되고 (1≤N≤105>, 0≤K≤N−1), 두 번째 줄에 소들의 품종 배치도가 G와 H로 이루어진 문자열로 주어진다. (G는 황소, H는 젖소를 의미한다)
Output
각 T번의 테스트케이스에 대하여 첫 번째 줄에 필요한 최소 풀의 개수, 두 번째 줄에 풀의 배치를 황소가 먹을 풀을 G로, 젖소가 먹을 풀을 H로, 그리고 아무 풀도 없는 곳을 .으로 표기한 길이 N의 문자열을 출력하시오.
Example
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
Source
USACO 2022 December Bronze
You must sign in to write code.