View problem - 마술 (GCJ14_magic)

Time limitMemory limit# of submissions# of submitted usersSolved #Accepted user ratio
1000 ms32 MiB1499100.00%

최근 여러분은 마술 쇼를 보러 갔습니다. 여러분은 카드 마술을 인상깊게 보았고, 이 마술의 비밀을 파헤치고자 합니다.

마술사는 16개의 카드를 $4 \times 4$ 크기의 정사각형 격자판에 놓으면서 마술을 시작합니다. 각 카드에는 1 이상 16 이하의 서로 다른 자연수가 적혀 있습니다. 그 다음, 마술사는 자원자에게 카드를 하나 골라서, 이 카드가 몇 번째 행에 있는지 말하라고 합니다.

마침내, 이 마술사는 격자판에 있는 16개의 카드를 재배열합니다. (다른 순서로 배열할 수도 있습니다) 한 번 더, 그는 자원자에게 그녀의 카드가 몇 번째 행에 있는지 묻습니다. 이 두 가지 질문에 대한 대답만으로, 마술사는 자원자가 고른 카드가 무엇인지 정확하게 알아냅니다. 놀랍죠?

여러분은 마술사의 기술을 이해하기 위해 프로그램을 작성하기로 합니다. 여러분의 프로그램은 두 개의 카드 배열과 각각의 질문에 대한 자원자의 대답(자신의 카드가 첫 번째 배열에서 몇 번째 행에 있는지, 두 번째 배열에서 몇 번째 행에 있는지)을 입력받을 것입니다. 행은 위에서 아래로 1부터 4까지의 번호가 붙어 있습니다.

여러분의 프로그램은 자원자가 고른 카드를 결정하거나, 자원자가 골랐을 수도 있는 카드가 1장보다 많다는 것을 판별하거나 (마술사가 실수를 했겠죠), 자원자의 대답에 해당하는 카드가 없다는 것을 판별해야 합니다. (자원자가 조작을 한 것입니다)

입력 형식

첫 번째 줄에 테스트 케이스의 수 $T$가 주어집니다. 이후 $T$개의 테스트 케이스가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 자원자의 첫 번째 질문에 대한 답을 나타내는 정수 하나가 주어집니다. 다음 4개의 줄에는 첫 번째 카드 배열이 주어집니다. 각 줄에는 공백을 사이로 두고 4개의 정수가 주어집니다. 그 다음 줄에는 자원자의 두 번째 질문에 대한 답을 나타내는 정수 하나가 주어지며, 그 다음 4개의 줄에는 두 번째 카드 배열이 위와 같은 형식으로 주어집니다.

출력 형식

각 테스트 케이스마다, "Case #x: y"를 출력합니다. x는 1부터 시작하는 테스트 케이스 번호입니다.

자원자가 골랐을 수도 있는 카드가 정확히 하나라면, y는 그 카드에 쓰여진 번호여야 합니다. 자원자가 골랐을 수도 있는 카드가 2장 이상이라면, y는 "Bad magician!" (따옴표 제외)여야 합니다. 자원자의 대답에 해당하는 카드가 하나도 없다면, y는 "Volunteer cheated!" (따옴표 제외)여야 합니다. 이 문자열은 정확해야 하므로, 여기서 복사/붙여넣기하는 것도 고려해 보세요.

제약 조건

  • $1 \le T \le 100$
  • $1 \le $ 자원자의 답 $\le 4$
  • 각 카드 배열에는 1 이상 16 이하의 정수가 정확히 한 번씩 등장합니다.

입력

3
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 5 4
3 11 6 15
9 10 7 12
13 14 8 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

출력

Case #1: 7
Case #2: Bad magician\!
Case #3: Volunteer cheated\!