Cow-libi 2

Đ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

$N$ con bò ngồi quanh đống lửa trại theo vòng tròn. Mỗi con bò thuộc về bác John (J) hoặc bác Nhoj (N). Bò của bác John luôn nói thật, còn bò của bác Nhoj luôn nói dối.

Các con bò được xếp hàng để thẩm vấn. Mỗi con bò thứ $i$ khai báo:

Hãy xác định xem có tồn tại cách sắp xếp vòng tròn và gán bác (J/N) cho mỗi con bò sao cho tất cả các khai báo đều nhất quán hay không.

Dòng đầu tiên chứa hai số nguyên $T$ ( $1 \leq T \leq 1000$ ) và $C$ ( $C \in {0, 1}$ ).
Với mỗi test case:
- Dòng 1: Số nguyên $N$ ( $2 \leq N \leq 10^{5}$ ).
- Dòng 2: Chuỗi $l_{1} l_{2} \dots l_{N}$ gồm $N$ ký tự J hoặc N (khai báo về bò bên trái).
- Dòng 3: Chuỗi $r_{1} r_{2} \dots r_{N}$ gồm $N$ ký tự J hoặc N (khai báo về bò bên phải).

Tổng $N$ trên tất cả test case không vượt quá $5 \times 10^{5}$ .

Với mỗi test case:

In YES hoặc NO.
Nếu C=1 và đáp án là YES, in thêm hai dòng:
- Hoán vị $p_{1}, p_{2}, \dots, p_{N}$ thể hiện thứ tự ngồi quanh vòng tròn.
- Chuỗi $b_{1} b_{2} \dots b_{N}$ gồm $N$ ký tự J hoặc N thể hiện bác mà mỗi con bò thuộc về.

Input	Output	Giải thích
6 0 3 JJJ JJJ 4 JJNJ NJJJ 6 NJNJNJ JNNJNJ 4 NNNN NNNN 3 NNN NNN 5 JJNNJ NJNJJ	YES NO NO YES NO YES	Test case 1: 3 bò đều khai JJ, có thể tất cả thuộc bác John ngồi cạnh nhau. Test case 4: 4 bò đều khai NN, xếp xen kẽ J và N.

Bình luận

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