레이팅 미적용베시에게 양의 정수 \(N\)과, 길이 \(3\)의 문자열 \(N\)개를 이어 붙여 만든 길이 \(3N\)의 문자열 \(S\)가 주어진다. 각 길이 \(3\)의 문자열은 "COW"의 순환 이동이다. 즉, 각 문자열은 "COW", "OWC", "WCO" 중 하나이다.
문자열 \(X\)가 제곱 문자열이라는 것은 \(X = Y + Y\)인 문자열 \(Y\)가 존재한다는 것과 동치이다. 여기서 \(+\)는 문자열 연결을 나타낸다. 예를 들어, "COWCOW"와 "CC"는 제곱 문자열이지만 "COWO"와 "OC"는 아니다.
한 번의 연산에서 베시는 \(S\)에서 제곱 문자열인 임의의 부분 수열 \(T\)를 제거할 수 있다. 문자열의 부분 수열이란 원래 문자열에서 몇 개(0개 가능)의 문자를 제거하여 얻을 수 있는 문자열이다.
베시가 \(S\)를 빈 문자열로 변환할 수 있는지 판별하는 것을 도와야 한다. 또한, 가능하다면 그 방법을 제시해야 한다.
베시에게는 \(0\) 또는 \(1\)인 매개변수 \(k\)도 주어진다. 구성에 사용된 연산의 수를 \(M\)이라 하자.
- \(k = 0\)이면, \(M\)은 가능한 최소 연산 수와 같아야 한다.
- \(k = 1\)이면, \(M\)은 가능한 최소 연산 수에 1을 더한 값까지 허용된다.
Problem credits: Aakash Gokhale
SCORING
- 입력 3-4: \(T \le 10, N \le 6, k = 0\)
- 입력 5-6: \(k = 1\)
- 입력 7-14: \(k = 0\)
Problem credits: Aakash Gokhale
첫째 줄에 독립적인 테스트 케이스의 수 \(T\) (\(1\le T\le 10^4\))와 \(k\) (\(0 \le k \le 1\))가 주어진다.
각 테스트 케이스의 첫째 줄에 \(N\) (\(1 \le N \le 10^5\))이 주어진다.
각 테스트 케이스의 둘째 줄에 \(S\)가 주어진다.
모든 테스트 케이스에 걸친 \(N\)의 합은 \(10^5\)를 넘지 않는다.
각 테스트 케이스에 대해 다음 절차에 따라 한 줄 또는 두 줄을 출력한다.
\(S\)를 빈 문자열로 변환하는 것이 불가능하면, 한 줄에 \(-1\)을 출력한다.
가능하다면, 첫째 줄에 구성에 사용된 연산의 수 \(M\)을 출력한다. 둘째 줄에 공백으로 구분된 \(3N\)개의 정수를 출력한다. \(i\)번째 정수 \(x\)는 \(S\)의 \(i\)번째 문자가 \(x\)번째 부분 수열의 일부로 삭제되었음을 나타낸다 (\(1 \le x \le M\)).
3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC-1
1
1 1 1 1 1 1 1 1 1 1 1 1
3
3 3 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1For the last test, the optimal number of operations is two, so any valid
construction with either \(M=2\) or \(M=3\) would be accepted.
For \(M=3\), here is a possible construction:
- In the first operation, remove the last twelve characters. Now we're left with COWCOW.
- In the second operation, remove the subsequence WW. Now we're left with COCO.
- In the last operation, remove all remaining characters.
3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC-1
1
1 1 1 1 1 1 1 1 1 1 1 1
2
1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > First Contest > Bronze