Chia Chuỗi COW

Đ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

Bessie nhận một số nguyên dương $N$ và một chuỗi $S$ độ dài $3 N$ . Chuỗi $S$ được tạo bằng cách nối $N$ chuỗi con, mỗi chuỗi con là một hoán vị vòng của "COW" (tức là "COW", "OWC", hoặc "WCO").

Một "chuỗi vuông" là chuỗi $X$ sao cho $X = Y + Y$ với chuỗi $Y$ nào đó. Ví dụ: "COWCOW" và "CC" là chuỗi vuông, nhưng "COWO" và "OC" thì không.

Mỗi thao tác, Bessie chọn một dãy con $T$ của $S$ sao cho $T$ là chuỗi vuông, rồi xóa các ký tự tương ứng khỏi $S$ . Mục tiêu là biến $S$ thành chuỗi rỗng.

Hãy xác định liệu có thể biến $S$ thành rỗng hay không, và nếu có, đưa ra cách thực hiện.

Dữ liệu vào

Dòng 1: Hai số nguyên $T$ và $k$ ( $k \in {0, 1}$ )
Với mỗi test case:
- Dòng 1: Số nguyên $N$
- Dòng 2: Chuỗi $S$ độ dài $3 N$

Dữ liệu ra

Với mỗi test case:

Nếu không thể: in $- 1$
Nếu có thể:
- Dòng 1: $M$ -- số thao tác
- Dòng 2: $3 N$ số nguyên cách nhau bởi dấu cách, số thứ $i$ cho biết ký tự thứ $i$ bị xóa ở thao tác nào (giá trị từ $1$ đến $M$ )

Ràng buộc

$1 \leq T \leq 10^{4}$
$0 \leq k \leq 1$
$1 \leq N \leq 10^{5}$
Tổng $N$ qua tất cả test case $\leq 10^{5}$

Ví dụ

Input	Output	Giải thích
3 1 3 COWOWCWCO 4 WCOCOWWCOCOW 6 COWCOWOWCOWCOWCOWC	-1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 2 1 1 1 1 1 1 1 2 1 1 2 1 1 1	$N = 3$ lẻ nên không thể. $N = 4$ : toàn bộ chuỗi là chuỗi vuông. $N = 6$ : cần 2 thao tác.

Bình luận

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