COW Splits
브론즈 II의견: 0
Bessie is given a positive integer \(N\) and a string \(S\) of length \(3N\) which is
generated by concatenating \(N\) strings of length \(3\), each of which is a cyclic
shift of "COW". In other words, each string will be "COW", "OWC", or "WCO".
String \(X\) is a square string if and only if there exists a string \(Y\)
such that \(X = Y + Y\) where \(+\) represents string concatenation. For example,
"COWCOW" and "CC" are examples of square strings but "COWO" and "OC" are not.
In a single operation, Bessie can remove any subsequence \(T\) from \(S\)
where \(T\) is a square string. A subsequence of a string is a string which can be
obtained by removing several (possibly zero) characters from the original
string.
Your job is to help Bessie determine whether it is possible to transform \(S\)
into an empty string. Additionally, if it is possible, then you must provide a
way to do so.
Bessie is also given a parameter \(k\) which is either \(0\) or \(1\). Let \(M\) be the
number of operations in your construction.
- If \(k = 0\), then \(M\) must equal the minimum possible number of operations.
- If \(k = 1\), then \(M\) can be up to one plus the minimum possible number of operations
Problem credits: Aakash Gokhale
SCORING
- Inputs 3-4: \(T \le 10, N \le 6, k = 0\)
- Inputs 5-6: \(k = 1\)
- Inputs 7-14: \(k = 0\)
Problem credits: Aakash Gokhale
The first line contains \(T\), the number of independent test cases
(\(1\le T\le 10^4\)) and \(k\) (\(0 \le k \le 1\)).
The first line of each test case has \(N\) (\(1 \le N \le 10^5\)).
The second line of each test case has \(S\).
The sum of \(N\) across all test cases will not exceed \(10^5\).
For each test case, output either one or two lines using the following
procedure.
If it is impossible to transform \(S\) into an empty string, print \(-1\) on a
single line.
Otherwise, on the first line print \(M\) -- the number of operations in your
construction. On the second line, print \(3N\) space-separated integers. The
\(i\)th integer \(x\) indicates that the \(i\)th letter of \(S\) was deleted as part of
the \(x\)th subsequence (\(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
평가 및 의견
COW Splits
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
COW Splits