레이팅 미적용농부 존에게는 \(N\)마리(\(1 \le {N} \le {10^5}\))의 소가 있으며, 각 소의 품종은 건지(Guernsey) 또는 홀스타인(Holstein)이다. 소들은 \(1\dots N\)의 번호가 붙은 위치를 차지하며 가로로 한 줄로 서 있다.
모든 소가 배가 고프므로, 농부 존은 \(1\dots N\)의 위치 중 일부에 풀밭을 심기로 한다. 건지와 홀스타인은 서로 다른 종류의 풀을 좋아하므로, 농부 존이 어떤 위치에 풀을 심기로 했다면 건지가 좋아하는 풀과 홀스타인이 좋아하는 풀 중 하나를 골라 심어야 한다 --- 같은 위치에 둘 다 심을 수는 없다. 심어진 각 풀밭은 해당 품종의 소를 무제한으로 먹일 수 있다.
각 소는 풀밭에 도달하기 위해 최대 \(K\)칸(\(0 \le {K} \le N-1\))까지 이동할 의향이 있다. 모든 소를 먹이는 데 필요한 풀밭의 최소 개수를 구하시오. 또한 그 최소 개수의 풀밭으로 소들을 먹이는 풀밭 배치를 하나 출력하시오. 위 조건을 만족하는 어떤 배치든 정답으로 인정된다.
출제: Mythreya Dharani
배점
- 입력 2부터 4까지는 \(N \le 10\)이다.
- 입력 5부터 8까지는 \(N \le 40\)이다.
- 입력 9부터 12까지는 \(N \le 10^5\)이다.
출제: Mythreya Dharani
각 입력은 \(T\)개의 테스트 케이스로 이루어지며, 각 케이스는 소들의 배치를 나타낸다. 입력의 첫째 줄에 \(T\) (\(1 \le T \le 10\))가 주어진다. 이어서 \(T\)개의 테스트 케이스가 주어진다.
각 테스트 케이스는 \(N\)과 \(K\)가 주어지는 줄로 시작한다. 다음 줄에 길이 \(N\)의 문자열이 주어지며, 각 문자는 \(i\)번째 소의 품종을 나타낸다(G는 건지, H는 홀스타인을 의미한다).
\(T\)개의 각 테스트 케이스에 대해 두 줄을 출력한다. 첫째 줄에는 소들을 먹이는 데 필요한 풀밭의 최소 개수를 출력한다. 둘째 줄에는 최소 개수의 풀밭으로 모든 소를 먹이는 배치를 나타내는 길이 \(N\)의 문자열을 출력한다. \(i\)번째 위치를 나타내는 \(i\)번째 문자는 풀밭이 없으면 '.', 건지를 먹이는 풀밭이 있으면 'G', 홀스타인을 먹이는 풀밭이 있으면 'H'여야 한다. 유효한 배치라면 모두 정답으로 인정된다.
6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH5
GHHGG
3
.GH.G
2
..GH.
2
...GH
2
...HG
2
HGNote that for some test cases, there are multiple acceptable configurations that
manage to feed all cows while using the minimum number of patches. For example,
in the fourth test case, another acceptable answer would be:
.GH..
This corresponds to placing a patch feeding Guernseys on the 2nd position and a
patch feeding Holsteins on the third position. This uses the optimal number of
patches and ensures that all cows are within 3 positions of a patch they prefer.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Bronze