만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

Joke

시간 제한2초메모리 제한512 MB

요약
두 플레이어의 시작 패, 덱 순서, 트럼프 무늬가 주어질 때 최적으로 둔다면 누가 이기는지, 또는 무승부인지 구합니다.
난이도

어려움10점 중 10점

유형
게임 이론, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

"Fool's Game"이라고 자주 불리는 카드 게임은 러시아에서 꽤 인기가 많다. 이 문제는 두 명이 54장의 덱(표준 카드 52장과 검은색, 빨간색 조커 한 장씩)으로 즐기도록 이 게임을 변형한 것을 다룬다.

스페이드와 클럽은 검은색이고, 하트와 다이아몬드는 빨간색이다. 조커에는 숫자와 무늬가 없고 색깔만 있다. 한 무늬가 트럼프로 지정된다.

처음에 각 플레이어는 카드를 6장씩 가진다. 나머지 42장은 어떤 순서로 쌓여 덱을 이룬다.

게임은 라운드 단위로 진행된다. 각 라운드 전에 한 플레이어는 공격자, 다른 플레이어는 방어자가 된다. 공격자는 같은 숫자의 카드를 한 장 이상 테이블에 내놓는다. 조커는 공격자가 내놓을 수 없다. 내놓는 카드 수는 방어자가 가진 카드 수를 넘을 수 없다. 방어자는 자신의 카드로 내놓인 카드를 모두 막는다. 막는 카드는 아직 막히지 않은 카드 위에 올린다. 어떤 카드가 다른 카드를 막을 수 있는 조건은 다음 중 하나 이상을 만족하는 경우다.

  • 같은 무늬이고 숫자가 더 높다. (숫자 순서는 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A이며 2가 가장 낮고 A가 가장 높다.)
  • 트럼프이고, 막히는 카드가 트럼프가 아니다. (트럼프는 더 높은 트럼프로만 막을 수 있다.)
  • 조커이고, 색깔이 막히는 카드의 색깔과 같다.
  • 조커이고, 색깔이 트럼프 무늬의 색깔과 같다.

테이블의 카드가 모두 막힌 뒤, 공격자는 막혀야 할 카드를 더 던질 수 있다. 조커는 공격자가 던질 수 없다. 던지는 카드의 숫자는 이미 테이블에 있는 카드의 숫자 중 하나와 같아야 한다. 새로 추가된 카드는 방어자가 막아야 한다. 그 뒤 공격자는 다시 카드를 더 던질 수 있으며, 이 과정이 반복된다. 공격자는 그 순간 방어자가 가진 카드 수보다 많은 카드를 던질 수 없다.

라운드는 두 가지 경우에 끝난다. 방어자가 막지 못하거나 막지 않겠다고 선언하면, 공격자는 테이블에 있는 숫자와 같은 카드를 더 던질 수 있다. 막히지 않은 카드 수는 방어자가 가진 카드 수를 넘을 수 없다. 그러면 방어자가 라운드에서 지고 테이블의 카드를 모두 자기 손에 넣는다. 공격자는 공격자 역할을 유지하고 다음 라운드에서도 다시 공격한다.

테이블의 카드가 모두 막혔고 공격자가 더 던지지 못하거나 던지지 않겠다고 하면, 방어자가 라운드에서 이기고 테이블의 카드는 게임에서 빠진다. 다음 라운드에서는 역할이 서로 바뀐다. 방어자가 공격자가 되고 공격자가 방어자가 된다.

라운드 사이에 직전 라운드의 공격자가 카드를 6장보다 적게 가지고 있으면, 덱 위에서 한 장씩 뽑아 6장이 될 때까지 채운다. 그다음 직전 라운드의 방어자도 같은 방식으로 채운다.

라운드를 시작하기 전에 한 플레이어는 카드가 없고 다른 플레이어는 한 장 이상 가지고 있으면, 카드가 없는 플레이어가 게임에서 이긴다. 두 플레이어 모두 카드가 없으면 무승부다. 두 플레이어 모두 한 장 이상 가지고 있지만, 다음 라운드의 공격자 카드가 모두 조커뿐이면 그 공격자는 아무 카드도 낼 수 없다. 게임은 끝나고 다음 라운드의 방어자가 이긴다.

요한이 첫 라운드의 공격자다. 트럼프 무늬, 두 플레이어의 초기 카드, 덱의 순서가 주어질 때 두 플레이어가 최적으로 플레이하면 누가 이기는지 구하라. 두 플레이어는 게임에 있는 모든 카드와 덱의 순서를 알고 있다.

입력

첫 줄에는 테스트 케이스의 수를 나타내는 정수 tt (1≤t≤1041 \le t \le 10^4)가 주어진다.

각 테스트 케이스는 네 줄로 주어진다. 첫 줄에는 요한의 카드 6장이, 둘째 줄에는 세바스찬의 카드 6장이 주어진다. 셋째 줄에는 덱의 카드 42장이 위에서 아래 순서로 주어진다. 넷째 줄에는 트럼프 무늬를 나타내는 문자 하나가 주어진다.

조커를 제외한 카드는 숫자('2'부터 '9', 10은 'T', 'J', 'Q', 'K', 'A')와 무늬('S'는 스페이드, 'C'는 클럽, 'D'는 다이아몬드, 'H'는 하트)를 차례로 적는다. 빨간색 조커는 "RJ", 검은색 조커는 "BJ"로 적는다. 각 테스트 케이스의 54장 카드는 모두 서로 다르다.

출력

각 테스트 케이스마다 승자의 이름을 한 줄에 출력한다. 승자는 "Johann" 또는 "Sebastian"이다. 게임이 무승부이면 "Bach"를 출력한다.

예제1

  1. 예제 1

    입력
    2
    TC QD 2S TH 4S 3C
    AS RJ AC 7D 6C BJ
    3D 4C 8C AD TD TS 7H JS KD 4H QC 6H 9D 7C 9H JC AH 5H 6S QH KS 5S 5D 3H JD JH 8H QS 2H 4D 5C 9S KH 6D 9C 8D 8S KC 7S 3S 2D 2C
    S
    TC 8S JS JD 5C 9C
    QS 8C 3H 4D 4H 2D
    QH 7S 7H 3C 2H 7C TD 9H 8D AH 7D QC JH 5D AS 5H 3D JC 2S 6D AC 9D 4C 6S KD 8H 6C 4S RJ KH 3S TS KC KS 5S QD 9S BJ 6H TH AD 2C
    D
    
    예상 출력
    Johann
    Sebastian