블랙 비엔나

시간 제한1초메모리 제한128 MB

요약
각 플레이어의 손패와 숨겨진 갱 카드, 심문 기록이 주어질 때, 자기 손패와 답변만으로 갱을 확정할 수 있게 되는 가장 이른 턴을 찾는다.
난이도

보통10점 중 6점

유형
완전 탐색, 조합론, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

이 문제는 보드게임 '블랙 비엔나(Black Vienna)'를 변형한 것입니다. 세 명의 플레이어가 참여하며, A부터 R까지의 문자가 적힌 카드 18장을 사용합니다.

  • 이 중 3장은 따로 빼내어 숨기며, 이 세 장을 갱(gang)이라고 부릅니다.
  • 남은 15장을 잘 섞어 각 플레이어에게 5장씩 나누어 줍니다.
  • 플레이어는 자신의 카드를 서로에게 절대 공개하지 않습니다.

또한 심문 카드 더미가 따로 있습니다. 각 심문 카드에는 서로 다른 세 개의 문자가 오름차순으로 적혀 있습니다(예: ACG, BHR).

차례는 플레이어 1 → 2 → 3 순서로 돌아갑니다. 자기 차례가 되면 플레이어는 심문 카드 하나를 골라 다른 플레이어 앞에 앞면으로 내려놓습니다. 지목된 플레이어는 그 카드에 적힌 세 문자 중 자신이 몇 장을 가지고 있는지 개수만 말해야 하며, 어떤 문자인지는 밝히지 않습니다. 예를 들어 어떤 플레이어가 심문 카드 ACG로 지목되었고 A와 G는 가지고 있지만 C는 없다면, 그 플레이어는 2라고 답합니다. 이 심문의 결과(누가 어떤 카드로 지목되었고 답이 몇이었는지)는 모든 플레이어가 함께 봅니다.

각 플레이어는 오직 자신의 카드 5장과 지금까지 공개된 모든 심문 결과만으로 추리합니다. 어떤 플레이어의 입장에서, 지금까지 알려진 정보와 모순되지 않는 갱의 조합이 정확히 하나뿐이라면 그 플레이어는 갱을 확신할 수 있습니다.

여러 게임의 기록이 주어질 때, 각 게임에서 어떤 플레이어든 갱을 확실히 알아낼 수 있게 되는 가장 이른 시점을 구하세요.

입력

입력은 1개 이상 12개 이하의 데이터 집합으로 이루어지며, 마지막에는 0만 적힌 줄이 옵니다.

각 데이터 집합의 형식은 다음과 같습니다.

  • 첫 줄: 기록된 차례의 수 tt (2≤t≤152 \le t \le 15).
  • 둘째 줄: 공백으로 구분된 네 개의 문자열. 차례대로 플레이어 1, 2, 3의 손패(각 5장)와 갱의 카드 3장입니다.
  • 이어지는 tt개의 줄: 각 차례의 기록이 순서대로 주어집니다. 각 줄은 공백으로 구분된 세 개의 토큰으로 이루어집니다 — 지목된 플레이어의 번호, 심문에 사용된 세 문자, 그리고 지목된 플레이어가 답한 개수입니다.

모든 문자열은 A부터 R까지의 대문자로만 이루어지며, 문자는 항상 오름차순으로 정렬되어 있습니다. 같은 심문 문자열이 한 게임에서 여러 차례에 걸쳐 나타날 수 있습니다.

출력

각 데이터 집합마다 한 줄을 출력합니다. 기록된 모든 차례가 끝난 뒤에도 어떤 플레이어도 갱을 확신할 수 없다면 문자 ?를 출력합니다. 어떤 플레이어가 갱을 알아낼 수 있다면, 한 명 이상의 플레이어가 갱을 확신할 수 있게 되는 가장 이른 차례의 번호를 출력합니다.

예제4

  1. 예제 1

    입력
    9
DGJLP EFOQR ACHMN BIK
2 BJK 0
3 ABK 1
2 DEF 2
2 EIL 1
3 FIP 0
1 GMO 1
2 OQR 3
3 ADQ 1
1 EGJ 2
3
ABCDE FGHIJ KLMNO PQR
3 BKQ 1
1 ADE 3
2 CHJ 2
0
    예상 출력
    8
?

  2. 예제 2

    입력
    12
ABCDE FGHIJ KLMNO PQR
2 FGH 3
2 HIJ 3
2 FIJ 3
3 KLM 3
3 MNO 3
3 KNO 3
2 FPQ 1
3 LPR 1
2 GIR 2
3 KMQ 2
2 HJP 2
3 LNR 2
0
    예상 출력
    5

  3. 예제 3

    입력
    2
ABCDE FGHIJ KLMNO PQR
2 PQR 0
3 PQR 0
0
    예상 출력
    2

  4. 예제 4

    입력
    3
ABCDE FGHIJ KLMNO PQR
2 ABF 1
2 PQR 0
3 PQR 0
0
    예상 출력
    3