페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8144
스페셜 저지
서브태스크
채점 보류

액체 정리 1s 1024MB

문제

갑순이는 최근 화학에 관심을 가지게 되었다. 현재 그녀는 서로 섞이지 않는 두 가지 색상, 1과 2으로 이루어진 다양한 액체를 다루고 있다.

갑순이가 갖고 있는 두 개의 시험관에는 각각 N 용량의 액체가 각기 다른 색상의 층으로 나누어져 들어 있다. 두 시험관의 액체는 각각 문자열 f_1f_2\ ...\ f_N과 s_1s_2\ ...\ s_N로 나타내며, f_i와 s_i는 시험관 바닥에서부터 i 단위만큼 떨어진 곳에 있는 액체의 색상을 의미한다. 반드시 두 색상 모두 포함되어 있음이 보장된다.

갑순이는 액체를 잘 정리하여 하나의 색상으로만 이루어진 두 개의 시험관으로 만들고자 한다. 이 과정에서 무한 용량의 빈 비커가 하나 제공되며, "붓기" 동작을 통해 각 시험관이나 비커에서 특정 색상의 액체를 다른 곳으로 옮길 수 있다. 모든 붓기 동작은 동일한 색상의 액체만 이동할 수 있다.

최소한의 붓기 횟수로 모든 액체를 정리하기 위해 필요한 붓기 횟수와 동작 시퀀스를 구하라. 두 시험관에 각각 어떤 색상이 들어 있는지는 중요하지 않으며, 최종적으로 비커는 비어 있어야 한다.


입력

첫 번째 줄에 테스트 케이스 수 T가 주어진다.
각 테스트 케이스는 다음과 같이 구성된다:

  • 첫 번째 줄: 정수 N과 P가 주어진다. N은 각 시험관에 채워진 액체의 용량, P는 쿼리 유형을 나타낸다.

  • 두 번째 줄: 문자열 f_1f_2\ ...\ f_N

  • 세 번째 줄: 문자열 s_1s_2\ ...\ s_N

f_i, s_i ∈ \{1, 2\}이며, 1은 색상 1의 액체, 2는 색상 2의 액체를 의미한다. f_1과 s_1은 시험관 바닥에 가까운 액체를 나타낸다.

[제약 조건]

  • 1 ≤ T ≤ 10

  • 1 ≤ N ≤ 10^5

  • 1 \le P \le 3


출력

각 테스트 케이스에 대해 다음을 출력한다.

  1. P = 1: 최소 붓기 횟수 M만 출력.

  2. P = 2: 붓기 횟수 A를 출력 (M ≤ A ≤ M + 5). 이후 A개의 줄에 걸쳐 각 줄에 "소스 시험관", "목적지 시험관" (1, 2 또는 3)으로 구성된 붓기 동작 출력.

  3. P = 3: 최소 붓기 횟수 M을 출력한 후, 정확히 M번의 붓기 동작을 출력.


부분문제

번호 점수 조건
#125점

P=1

#225점

P=2

#350점

추가 제약 조건 없음


예제 

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222
4
4
1 2
1 3
2 1
3 2
4
1 2
1 3
2 1
3 2
1
2 1
5
2 3
1 2
1 3
1 2
3 1
6
2 3
1 2
1 3
1 2
2 1
3 2

첫 세 개의 테스트 케이스에서 최소 붓기 횟수는 4이다. 출력된 동작을 통해 각 시험관이 단일 색상으로 채워질 수 있음을 확인할 수 있다.

초기 상태:

1: 1221
2: 2211
3:

"1 2" 이동 후:

1: 122
2: 22111
3:

"1 3" 이동 후:

1: 1
2: 22111
3: 22

"2 1" 이동 후:

1: 1111
2: 22
3: 22

"3 2" 이동 후:

1: 1111
2: 2222
3:

마지막 테스트 케이스에서 최소 붓기 횟수는 5이지만, P=2이므로 6번의 동작도 허용된다.


출처

USACO 2024 February Silver 2번

로그인해야 코드를 작성할 수 있어요.