시험관

베시가 최근 화학에 푹 빠졌다. 지금 베시에게는 서로 잘 섞이지 않는 여러 액체가 색 \(1\)과 \(2\)의 두 가지 색으로 있다. 용량이 무한한 시험관 두 개가 있고, 각 시험관에는 이 두 색 액체의 어떤 혼합물이 \(N\) \((1 \leq N \leq 10^5)\)단위씩 들어 있다. 액체들은 섞이지 않으므로 가라앉은 뒤에는 색별로 층이 나뉜다. 따라서 두 시험관은 문자열 \(f_1f_2\ldots f_N\)과 \(s_1s_2\ldots s_N\)으로 볼 수 있는데, \(f_i\)는 첫 번째 시험관의 바닥에서 \(i\)단위 떨어진 곳에 있는 액체의 색이고, \(s_i\)는 두 번째 시험관의 바닥에서 \(i\)단위 떨어진 곳에 있는 액체의 색이다. 각 색의 액체가 적어도 1단위씩 존재함이 보장된다.

베시는 각 시험관이 한 가지 색의 액체만 모두 담도록 액체들을 분리하고 싶다. 이 작업을 돕기 위해 용량이 무한한 빈 비커가 하나 더 있다. 베시가 "붓기"를 한 번 하면, 어떤 시험관이나 비커의 맨 위에 있는 색 \(i\)의 액체 전부를 다른 곳으로 옮긴다.

모든 액체를 두 시험관으로 분리하는 데 필요한 최소 붓기 횟수와 그에 필요한 일련의 이동을 구하여라. 어느 시험관에 어느 색이 들어가든 상관없지만, 비커는 비어 있어야 한다.

\(T\) (\(1 \leq T \leq 10\))개의 테스트 케이스가 있으며, 각 테스트 케이스마다 매개변수 \(P\)가 주어진다.

액체를 원래의 두 시험관으로 분리하는 최소 붓기 횟수를 \(M\)이라 하자.

• \(P=1\)이면, \(M\)만 출력하면 정답으로 인정된다.
• \(P=2\)이면, \(M \leq A \leq M+5\)인 정수 \(A\)를 출력한 뒤, 그 횟수로 해를 구성하는 \(A\)개의 줄을 출력하면 정답으로 인정된다. 각 줄에는 출발지와 도착지 시험관(\(1\), \(2\), 또는 비커는 \(3\))을 출력해야 한다. 이동 전에 출발지는 비어 있으면 안 되고, 자기 자신에게 부을 수 없다.
• \(P=3\)이면, \(M\)을 출력한 뒤 그 횟수를 사용하는 유효한 구성을 출력하면 정답으로 인정된다.

출제: Suhas Nagar

배점

• 입력 2-6: \(P = 1\)
• 입력 7-11: \(P=2\)
• 입력 12-21: 추가 제약 없음.

또한 예제를 제외한 모든 입력에서 \(T=10\)임이 보장된다.

출제: Suhas Nagar

첫째 줄에 테스트 케이스의 개수 \(T\)가 주어진다. 각 테스트 케이스마다, 다음 줄에 각 시험관에 처음 채워진 양과 질의 유형을 나타내는 \(N\)과 \(P\)가 주어진다. 그다음 줄에 첫 번째 시험관을 나타내는 \(f_1f_2f_3\ldots f_N\)이 주어진다. \(f_i \in \{ 1,2 \}\)이고 \(f_1\)은 시험관의 바닥을 나타낸다. 그다음 줄에 두 번째 시험관을 나타내는 \(s_1s_2s_3\ldots s_N\)이 주어진다. \(s_i \in \{ 1,2 \}\)이고 \(s_1\)은 시험관의 바닥을 나타낸다.

두 입력 문자열 전체에 걸쳐 \(1\)과 \(2\)가 각각 적어도 하나씩 있음이 보장된다.

각 테스트 케이스마다, 시험관의 액체를 분리하는 최소 붓기 횟수를 나타내는 수 하나를 출력한다. 질의 유형에 따라 유효한 구성도 함께 출력해야 할 수 있다.

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > February > Silver