RiseOJ – 교환으로 이기기

설명

농부 존은 $$M$$ 개의 문자로 이루어진 가장 좋아하는 문자열 $$t$$ 를 가지고 있다. 또한 각각 $$M$$ 개의 문자로 이루어진 $$N$$ 개의 문자열 $s_1, s_2, \ldots, s_N$ 도 가지고 있다 ( $1 \leq N, M \leq 1000$ ).

농부 존은 다음 두 종류의 연산을 수행할 수 있다.

임의의 문자열 $$s_x$$ 와 두 인덱스 $$p$$ , $$q$$ 를 선택한다. 그런 다음 $$s_x$$ 의 $$p$$ 번째 문자와 $$q$$ 번째 문자를 교환한다 ( $1\le x\le N, 1\le p,q\le M$ ).
두 문자열 $$s_x$$ , $$s_y$$ 와 인덱스 $$k$$ 를 선택한다. 그런 다음 $$s_x$$ 와 $$s_y$$ 의 $$k$$ 번째 문자를 교환한다 ( $1\le x,y\le N, 1\le k\le M$ ).

그의 목표는 $$s_1$$ 을 $$t$$ 와 같게 만드는 것이다. 목표를 달성하는 임의의 연산 수열을 찾으시오. 농부 존은 바쁘기 때문에 총 $$2M$$ 번의 연산만 수행할 시간이 있다. 입력은 농부 존의 목표를 달성하는 것이 가능함을 보장한다.

문제 제공: Chongtian Ma

제약

채점 방식

입력 2-6: $N, M \le 100$
입력 7-12: 추가 제약 조건이 없다.

문제 제공: Chongtian Ma

입력 형식

첫째 줄에 독립적인 테스트의 수 $$T$$ ( $1\le T\le 10$ )가 주어진다. 각 테스트는 다음 형식으로 주어진다.

첫째 줄에 $$N$$ 과 $$M$$ 이 주어진다.

둘째 줄에 $$t$$ 가 주어진다.

그다음 $$N$$ 개의 줄이 이어지며, 그중 $$i$$ 번째 줄에 $$s_i$$ 가 주어진다.

입력은 농부 존의 목표를 달성하는 것이 가능함을 보장한다. 모든 문자열은 영어 소문자(a-z)로 이루어진다.

출력 형식

각 테스트에 대한 출력은 다음과 같아야 한다.

첫째 줄에 수행할 연산의 수인 정수 $$K$$ 를 출력한다. $$K$$ 는 $$2M$$ 이하의 음이 아닌 정수여야 한다.

그다음 수행할 연산을 순서대로 나타내는 $$K$$ 개의 줄을 출력한다. 각 줄은 다음 중 하나여야 한다.

$\texttt{1 x p q}$
$\texttt{2 x y k}$

예제 1

입력

3
3 6
banana
nabana
banana
nnbaaa
5 3
abc
def
bca
ghi
jkl
mno
3 5
abcde
abcde
abcde
zzzzz

출력

설명

Here is how $$s$$ changes according to the first test's output (with letters
swapped in uppercase):

nabana    Babana    baNaBa    banaNa
banana -> Nanana -> nanana -> nanaBa
nnbaaa    nnbaaa    nnbaaa    nnbaaa

After all three operations, $$s_1=t$$ .

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > Third Contest > Bronze

올림피아드 > USACO > 2025-2026 > Third Contest > Bronze

태그

JudgeUSACO

교환으로 이기기

평가 및 의견

풀이 제출