Hoán Đổi Để Thắng

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Bác John có một chuỗi mục tiêu $t$ gồm $M$ ký tự và $N$ chuỗi $s_{1}, s_{2}, \dots, s_{N}$ , mỗi chuỗi gồm $M$ ký tự (đều là chữ cái tiếng Anh thường).

Có hai phép biến đổi:

Hoán vị trong chuỗi: Chọn chuỗi $s_{x}$ và hai vị trí $p, q$ . Hoán đổi ký tự thứ $p$ và thứ $q$ của $s_{x}$ .
Hoán vị giữa hai chuỗi: Chọn hai chuỗi $s_{x}, s_{y}$ và vị trí $k$ . Hoán đổi ký tự thứ $k$ của $s_{x}$ và $s_{y}$ .

Biến đổi $s_{1}$ thành $t$ sử dụng tối đa $2 M$ phép biến đổi. Đảm bảo luôn tồn tại lời giải.

Dữ liệu vào

Dòng 1: Số nguyên $T$ — số bộ test ( $1 \leq T \leq 10$ )
Với mỗi bộ test:
- Dòng 1: Hai số nguyên $N$ và $M$
- Dòng 2: Chuỗi mục tiêu $t$
- $N$ dòng tiếp theo: Các chuỗi $s_{1}, s_{2}, \dots, s_{N}$

Dữ liệu ra

Với mỗi bộ test:

Dòng 1: Số nguyên $K$ ( $0 \leq K \leq 2 M$ ) — số phép biến đổi
$K$ dòng tiếp theo: Mỗi dòng mô tả một phép biến đổi theo định dạng 1 x p q hoặc 2 x y k

Ràng buộc

$1 \leq N, M \leq 1000$
Tất cả chuỗi gồm chữ cái tiếng Anh thường
Luôn tồn tại lời giải

Ví dụ

Input	Output	Giải thích
3 3 6 banana nabana banana nnbaaa 5 3 abc def bca ghi jkl mno 3 5 abcde abcde abcde zzzzz	1 1 1 1 3 5 1 2 3 1 2 1 2 1 1 2 3 2 2 1 2 2 2 1 2 3 0	Test 1: Hoán đổi vị trí 1 và 3 trong $s_{1}$ . Test 3: $s_{1}$ đã bằng $t$ .

Ghi chú

Test 2-6: $N, M \leq 100$
Test 7-12: Không ràng buộc bổ sung

Bình luận

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