Cho Bò Ăn

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John quản lý $N$ con bò ( $1 \leq N \leq 10^{5}$ ) đứng tại các vị trí từ $1$ đến $N$ . Mỗi con bò thuộc giống Guernsey (G) hoặc Holstein (H). Farmer John cần trồng các ô cỏ để cho bò ăn. Mỗi ô cỏ chứa loại cỏ dành cho Guernsey hoặc Holstein.

Mỗi con bò có thể di chuyển tối đa $K$ vị trí ( $0 \leq K \leq N - 1$ ) để đến một ô cỏ phù hợp với giống của nó. Hãy tìm số ô cỏ tối thiểu cần trồng sao cho mọi con bò đều được cho ăn, và đưa ra một cách bố trí hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa $T$ ( $1 \leq T \leq 10$ ), số lượng bộ test.
Với mỗi bộ test:
- Dòng 1: hai số nguyên $N$ và $K$ .
- Dòng 2: xâu ký tự độ dài $N$ gồm các ký tự 'G' và 'H'.

Dữ liệu ra

Với mỗi bộ test, in ra hai dòng:

Dòng 1: số ô cỏ tối thiểu cần trồng.
Dòng 2: xâu ký tự độ dài $N$ , mỗi vị trí là '.' (không trồng), 'G' (cỏ Guernsey), hoặc 'H' (cỏ Holstein).

Ràng buộc

$1 \leq N \leq 10^{5}$
$0 \leq K \leq N - 1$
$1 \leq T \leq 10$

Ví dụ

Input	Output	Giải thích
2 5 0 GHHGG 5 2 GHHGG	5 GHHGG 2 ..GH.	Khi $K = 0$ , mỗi con bò cần ô cỏ ngay tại vị trí của nó. Khi $K = 2$ , chỉ cần 2 ô cỏ.

Bình luận

Không có bình luận tại thời điểm này.