¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#8841
Juez especial
Subtarea

COW 분할 1s 1024MB

Problemas

베시는 양의 정수 N과 길이가 3N인 문자열 S를 받는다. S는 길이 3인 문자열 N개를 이어 붙여 만들어지며, 각 길이 3 문자열은 "COW"의 순환 이동(cyclic shift)이다. 즉, 각 문자열은 "COW", "OWC", "WCO" 중 하나이다.

문자열 X가 제곱 문자열(square string)이라는 것은, 어떤 문자열 Y가 존재하여 X = Y + Y 를 만족할 때이자 그때에만 성립한다. 여기서 +는 문자열 이어 붙이기(concatenation)를 의미한다. 예를 들어 "COWCOW"와 "CC"는 제곱 문자열이지만, "COWO"와 "OC"는 제곱 문자열이 아니다.

한 번의 연산에서, 베시는 S에서 어떤 부분수열(subsequence) T를 제거할 수 있는데, 이때 T는 제곱 문자열이어야 한다. 문자열의 부분수열이란, 원래 문자열에서 몇 개(0개일 수도 있음)의 문자를 삭제해서 얻을 수 있는 문자열을 말한다.

당신의 임무는 베시가 S를 빈 문자열로 만들 수 있는지(모든 문자를 제거할 수 있는지) 판단하는 것이다. 또한 가능하다면, 그 방법을 하나 제시해야 한다.

베시는 또한 매개변수 k(0 또는 1)를 받는다. 당신이 제시한 구성에서 사용한 연산 횟수를 M이라고 하자.

  • k = 0이면, M은 가능한 연산 횟수의 최솟값과 정확히 같아야 한다.

  • k = 1이면, M은 가능한 최솟값보다 최대 1만큼 더 커도 된다.


Entrada

첫 줄에 독립적인 테스트 케이스 수 T(1 ≤ T ≤ 10^4)와 k(0 ≤ k ≤ 1)가 주어진다.

각 테스트 케이스는 다음과 같다:

  • 첫 줄에 N(1 ≤ N ≤ 10^5)

  • 둘째 줄에 문자열 S

모든 테스트 케이스에 대한 N의 합은 10^5을 넘지 않는다.


Salida

각 테스트 케이스마다 다음 절차에 따라 한 줄 또는 두 줄을 출력한다.

  • 만약 S를 빈 문자열로 만드는 것이 불가능하면, 한 줄에 -1을 출력한다.

  • 가능하다면,

    • 첫 줄에 연산 횟수 M을 출력한다.

    • 둘째 줄에 3N개의 정수를 공백으로 구분해 출력한다. i번째 정수 x는 S의 i번째 글자가 x번째 부분수열을 제거하는 과정에서 삭제되었음을 의미한다(1 ≤ x ≤ M).


Subtarea

# Puntaje Condición
#120

T≤10,\ N≤6,\ k=0

#230

k=1

#350

k=0


Ejemplo #1

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 1

마지막 테스트의 경우, 최적(최소) 연산 횟수는 2이므로, M = 2 또는 M = 3인 어떤 유효한 구성도 정답으로 인정된다.

M = 3인 한 가지 가능한 구성은 다음과 같다:

  • 첫 번째 연산에서 마지막 12개의 문자를 제거한다. 그러면 남는 것은 "COWCOW"이다.

  • 두 번째 연산에서 부분수열 "WW"를 제거한다. 그러면 남는 것은 "COCO"이다.

  • 마지막 연산에서 남아 있는 모든 문자를 제거한다.


Ejemplo #2

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 2


Fuente

USACO 2026 First Contest, Bronze
Debes iniciar sesión para escribir código.