cho.sh

Go++ (Small)

1로만 이루어진 나쁜 문자열 B와 길이 L인 이진 문자열 집합 G가 주어질 때, 교차 실행으로 G의 모든 문자열을 출력할 수 있으면서 B는 절대 출력하지 않는 Go++ 프로그램 두 개가 존재하는지 판정한다.

보통6구현시뮬레이션그리디조합론아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

Go 언어는 API가 단순하고 멀티스레딩을 지원하도록 설계되었다. Code Jam 팀은 이 목표를 극한까지 밀어붙이고 싶어서 Go++라는 새 언어를 제안한다.

Go++에는 레지스터가 하나 있고, 이 레지스터는 불리언 값(0 또는 1) 하나를 저장한다. 레지스터의 초깃값은 0이다. 명령어는 세 가지다.

  • 0: 레지스터를 0으로 설정한다.
  • 1: 레지스터를 1로 설정한다.
  • ?: 현재 레지스터 값을 출력한다.

간단하지 않은가? 멀티스레딩을 지원하기 위해 서로 다른 Go++ 프로그램 두 개가 레지스터 하나를 공유하며 동시에 실행될 수 있다. 각 명령어는 원자적으로 실행된다. 즉 한 명령어가 완전히 끝나야 다음 명령어가 시작된다. 두 프로그램의 명령어는 각 프로그램 안의 상대적인 순서만 지킨다면 어떤 방식으로든 섞일 수 있다.

예를 들어 두 프로그램 1?과 ?0을 함께 실행하는 방법은 아래 여섯 가지뿐이다. 두 번째 프로그램의 명령어에는 작은따옴표(')를 붙여 첫 번째 프로그램의 명령어와 구분했다.

  • ?'0'1?: 01을 출력한다. (레지스터의 초깃값이 0이라는 점을 기억하자.)
  • ?'10'?: 00을 출력한다.
  • ?'1?0': 01을 출력한다.
  • 1?'0'?: 10을 출력한다.
  • 1?'?0': 11을 출력한다.
  • 1??'0': 11을 출력한다.

레지스터가 ? 상태일 수는 없으므로 출력 문자열은 항상 0과 1로만 이루어지고 ?는 나오지 않는다.

보통 프로그래머는 원하는 출력을 내는 프로그램을 작성하지만, 이 문제에서는 원하지 않는 출력을 내지 않는 프로그램 두 개를 작성해야 한다. 구체적으로, 길이가 L인 "나쁜" 문자열 B와 길이가 모두 L인 "좋은" 문자열 N개의 집합 G가 주어진다. 두 Go++ 프로그램(길이가 같을 필요는 없다)을 만들되, 위에서 설명한 방식으로 실행했을 때 G의 모든 문자열을 출력할 수 있고 B는 출력할 수 없어야 한다. B도 아니고 G에도 없는 다른 문자열을 출력할 수 있어도 괜찮다. 두 프로그램에 들어 있는 ? 명령어는 합쳐서 정확히 L개여야 한다. 두 프로그램의 명령어 수를 합한 값은 200을 넘으면 안 된다.

예를 들어 B = 11, G = { 10, 00 }이면 프로그램 ?과 10?1은 올바른 답 중 하나다. 이 두 프로그램은 G의 모든 문자열을 출력할 수 있고, 어떻게 섞어도 B는 출력할 수 없다. (01도 출력할 수 있지만 이 문자열은 B도 아니고 G에도 없으므로 상관없다.) 반면 프로그램 1?과 ?0은 위에서 본 것처럼 B를 출력할 수 있으므로 올바른 답이 아니다. 프로그램 00과 ??는 G의 모든 문자열을 출력할 수 없으므로 올바른 답이 아니다.

조건을 만족하는 두 프로그램을 만들거나, 그런 프로그램이 없어서 IMPOSSIBLE인지 판별하라.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에는 G에 속한 문자열의 수 N과, B와 G의 문자열의 길이 L이 주어진다. 둘째 줄에는 G에 속한 서로 다른 길이 L의 문자열 N개가 공백으로 구분되어 주어진다. 셋째 줄에는 길이가 L인 나쁜 문자열 B가 주어진다. B와 G의 모든 문자열은 0과 1로만 이루어진다.

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤1001 \le N \le 100
  • 1≤L≤501 \le L \le 50
  • G의 문자열은 모두 서로 다르다.
  • B는 1로만 이루어진다.

출력

각 테스트 케이스마다 한 줄을 출력한다.

조건을 만족하는 두 프로그램이 없으면 Case #x: IMPOSSIBLE을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호다.

조건을 만족하는 두 프로그램이 있으면 Case #x: y z를 출력한다. 여기서 y와 z가 두 프로그램이다. 두 프로그램의 명령어 수를 합한 값은 200을 넘으면 안 되고, 각 프로그램에는 명령어가 하나 이상 있어야 하며, 두 프로그램의 ? 명령어는 합쳐서 정확히 L개여야 한다. 올바른 답은 여러 개일 수 있으므로, 이 문제에서는 반드시 다음 두 프로그램을 출력해야 한다.

  • y는 10을 L−1L-1번 이어 쓴 뒤 ?1을 붙인 프로그램이다.
  • z는 0 뒤에 ?를 L−1L-1개 붙인 프로그램이다.

올바른 답이 하나라도 있으면 이 두 프로그램도 항상 조건을 만족한다. 예를 들어 L = 3이면 Case #x: 1010?1 0??를 출력한다.

힌트

예제의 1번 테스트 케이스는 문제 본문에서 설명한 경우다. 출력 규칙에 따라 답은 10?1 0?이다.

예제의 2번 테스트 케이스는 B가 G에 들어 있으므로 당연히 IMPOSSIBLE이다.