문제1148--타짜

1148: 타짜

시간제한 : 10.000 sec  메모리제한 : 128 MB  Special Judge

문제 설명

평소 맞고를 즐겨하는 라미.
영준이와 게임을 할 때마다 돈을 잃는 것에 화가난 라미는 광성이에게 치팅 프로그램을 의뢰한다.
영준이와의 고스톱 게임을 유심히 지켜본 광성이는 영준이의 패턴을 발견하였다. 그가 화투패를 내는 규칙은 의외로 간단했다. 먼저 그는 48장의 카드들에 우선순위를 부여한 후, 먹을 수 있는 패 중 가장 우선순위가 높은 패를 내려놓는다. 만약 먹을 것이 없으면 들고 있는 패 중에서 가장 우선순위가 낮은 패를 내려놓는다.
랜덤하게 섞인 화투와 영준이의 우선순위가 주어졌을 때, 라미가 이기기 위해 내야하는 패의 순서를 출력하시오. 정답이 여러개일 경우 무작위로 1가지를 출력하며, 만약 이기는 것이 불가능할 경우 "IMPOSSIBLE" 을 출력한다.
화투와 게임 룰은 다음과 같다.
화투 패 - 도박은 위험합니다, 이 그림을 보고 손이 떨리거나 그러면 지금바로 도박상담을..
화투의 총 48장의 패는 1월부터 12월까지 달을 나누고, 각 달에 해당하는 패가 4장씩 존재하는 것으로 위의 그림과 같이 구성된다.
편의상 각 월의 패에 차례대로 A, B, C, D를 붙이자.
즉, 1A 는 1월의 첫번째 패를, 12D는 12월의 마지막 패를 의미한다.
맞고는 화투로 하는 카드 게임 중 하나로 두명이서 진행을 한다. 영준이와 라미는 맞고를 아래와 같은 방법으로 진행을 하고 있다.
*화투에서 패를 먹는것은, 바닥에 있는 패 중에서 내려놓는 패와 월이 같은 패 1장을 같이 가져가는것을 의미한다.
  1. 게임은 항상 영준이가 먼저 시작한다.
  2. 패를 돌린다. 처음 10장은 영준이가 갖고, 다음 10장은 라미가 갖는다. 다음 8장을 바닥에 깔고, 나머지 20장을 더미에 쌓는다. 이때 앞에 있는 패가 가장 아래에, 마지막 패가 가장 위에 놓여지게 된다.
  3. 영준이가 손에 들고 있는 패 중에서 바닥에 있는 패를 먹을 수 있는 것 부터 먼저 내려 놓는다.
    • 바닥의 패를 먹을 수 있는 패가 여러장 일 경우 그 중 가장 우선순위가 높은 패 부터 내려 놓는다.
    • 바닥에 있는 패 중에서 내려놓은 패와 월이 같은 패 1장을 같이 가져간다. 동일한 월의 패가 바닥에 여러장 있을 경우 A, B, C, D 순으로 1장만 가져간다.
    • 바닥에 먹을 수 있는 패가 없는 경우, 전체 패 중에서 가장 우선순위가 낮은 패를 내려 놓는다.
  4. 영준이가 더미의 가장 위에서 패를 뒤집어 바닥에 내려놓는다.
    • 바닥에 있는 패 중에서 내려놓은 패와 월이 같은 패 1장을 같이 가져간다. 동일한 월의 패가 바닥에 여러장 있을 경우 A, B, C, D 순으로 1장만 가져간다.
    • 바닥에 동일한 월의 패가 없는 경우 뒤집은 패를 바닥에 둔다.
  5. 라미가 손에 들고 있는 패를 내려 놓는다.
    • 바닥에 있는 패 중에서 내려놓은 패와 월이 같은 패 1장을 같이 가져간다. 동일한 월의 패가 바닥에 여러장 있을 경우 A, B, C, D 순으로 1장만 가져간다.
    • 바닥에 동일한 월의 패가 없는 경우 바닥에 그대로 둔다.
  6. 라미가 더미의 가장 위에서 패를 뒤집어 바닥에 내려놓는다.
    • 바닥에 있는 패 중에서 내려놓은 패와 월이 같은 패 1장을 같이 가져간다. 동일한 월의 패가 바닥에 여러장 있을 경우 A, B, C, D 순으로 1장만 가져간다.
    • 바닥에 동일한 월의 패가 없는 경우 뒤집은 패를 바닥에 둔다.
  7. 서로의 패를 다 소진할 때까지 3 ~ 6을 반복한다.
  8. 게임이 끝나면 각자가 먹은 패를 아래 점수 계산 방법에 따라 점수를 계산하여 승자를 가린다.
최종 점수 계산은 다음과 같다.
  • 광: [1A, 3A, 8A, 11A, 12A] 중 3개를 먹었을 경우 3점, 4개일 경우 4점, 5개일 경우 15점
  • 멍따: [2A, 4A, 5A, 6A, 7A, 8B, 10A, 12B] 중 5개를 먹었을 경우 1점, 6개 2점, 7개 3점. 8개 4점.
  • 고도리: [2A, 4A, 8B] 를 모두 모으면 5점.
  • 청단: [6B, 9B, 10B] 를 모두 모으면 3점.
  • 홍단: [1B, 2B, 3B] 를 모두 모으면 3점.
  • 초단: [4B, 5B, 7B] 를 모두 모으면 3점.
  • 띠: [1B, 2B, 3B, 4B, 5B, 6B, 7B, 9B, 10B, 12C] 중 5개를 먹었을 경우 1점. 이후 1개 먹을때마다 1점씩 증가. (5개 1점, 6개 2점, ...)
  • 피점수: [9A, 11B, 1C, 2C, 3C, 4C, 5C, 6C, 7C, 8C, 9C, 10C, 11C, 1D, 2D, 3D, 4D, 5D, 6D, 7D, 8D, 9D, 10D, 11D, 12D] 중 10개 이상부터 1점씩 증가. (10개 1점, 11개 2점, 12개 3점.....)
문제 이해를 위해 도움말을 반드시 참고하세요

입력 설명

첫 줄에는 테스트 케이스 개수 T (1 <= T <= 20)가 주어진다.
그 다음 각 테스트 케이스 별로 두 줄에 걸쳐 입력이 주어진다.
첫 번째 줄에는 영준이의 패 우선순위가 한 줄로 주어진다. 1A, 1B, 1C, 1D, 2A, ..., 12C, 12D 순서대로 0부터 47까지 부여되며 숫자가 작을수록 우선순위가 높다.
두 번째 줄에는 무작위로 섞인 화투패가 주어진다.
주어진 화투는 라미가 이길 수 있는 화투도 있고, 절대 이길 수 없는 화투도 있다.
만약 라미가 이길 수 있는 화투패일 경우, 승률은 50%가 넘는다.

출력 설명

테스트 케이스마다 라미가 이길 수 있는 패 순서 중 1개를 한줄로 출력한다. 만약 이길 수 없는 경우 "IMPOSSIBLE" 을 출력한다.

입력 예시 Copy

2
33 11 24 18 3 12 5 37 45 10 32 34 29 46 30 9 26 25 19 40 38 16 44 13 43 14 42 22 7 41 0 35 39 2 17 28 20 4 6 27 23 15 8 47 1 31 21 36
7B 6B 5C 1B 6C 11B 11C 10B 10D 7C 3A 3C 9D 12C 8C 2A 8A 4A 6D 8D 6A 8B 3D 12A 10A 3B 7D 9B 4B 9C 4D 12B 7A 11A 2D 5A 1D 9A 12D 1A 5D 11D 2C 10C 4C 2B 1C 5B
41 38 22 6 39 4 9 0 13 24 35 23 14 15 5 43 42 1 40 7 28 3 10 36 45 12 32 20 16 31 21 17 19 18 33 47 37 8 11 34 29 26 27 44 25 2 30 46
10D 2C 10C 11D 11B 2D 7B 5D 4A 7D 6C 9B 1D 7A 8D 12A 8C 12D 4B 4D 3B 8A 1C 6B 9A 5B 3C 7C 4C 5A 3D 11A 6A 9C 11C 6D 12B 1B 10B 1A 2B 9D 2A 3A 5C 12C 10A 8B

출력 예시 Copy

8D 9D 3C 8C 6D 4A 2A 12C 3A 8A
IMPOSSIBLE

도움

첫 번째 테스트 케이스의 경우,
임의로 섞인 화투패 중에서,
첫 10장 [7B 6B 5C 1B 6C 11B 11C 10B 10D 7C] 이 영준이의 패이고,
다음 10장 [3A 3C 9D 12C 8C 2A 8A 4A 6D 8D] 이 라미의 패이고,
다음 8장 [6A 8B 3D 12A 10A 3B 7D 9B] 이 바닥에 깔린다.
나머지 20장 [4B 9C 4D 12B 7A 11A 2D 5A 1D 9A 12D 1A 5D 11D 2C 10C 4C 2B 1C 5B] 이 더미에 쌓인다.
라미는 정답에 주어진 순서 [8D 9D 3C 8C 6D 4A 2A 12C 3A 8A] 대로 패를 낸다고 하자. 즉, 라미는 영준이와 달리 우선순위가 없고 무조건 순서대로 패를 낸다.
영준이의 손에 든 패를 우선순위별로 나열하면 [10B 11C 1B 7B 11B 6B 5C 10D 7C 6C] 이다.
바닥에 깔린 [6A 8B 3D 12A 10A 3B 7D 9B] 중에서 영준이가 먹을 수 있는 패 중 가장 우선순위가 높은 패는 10B 이다. 따라서 10B를 내고, 10A를 먹으며, 더미의 가장 뒤에 있는 5B를 바닥에 낸다. 5B와 같은 월의 패는 없으므로 영준이는 10A, 10B 를 먹는다.
다음으로 라미가 8D를 내고, 더미의 뒤에서 1C를 낸다. 바닥에 있는 패 중 8B를 먹을 수 있으므로 라미는 8B, 8D 를 먹는다.
두 사람의 첫 턴이 지난 후 패의 상태는 다음과 같다.
영준: [11C 1B 7B 11B 6B 5C 10D 7C 6C]     먹은패: [10A 10B]
라미: [9D 3C 8C 6D 4A 2A 12C 3A 8A] 먹은패: [8B, 8D]
바닥: [6A 3D 12A 3B 7D 9B 5B 1C]
더미: [4B 9C 4D 12B 7A 11A 2D 5A 1D 9A 12D 1A 5D 11D 2C 10C 4C 2B]
최종적으로 두 사람이 먹은 패는 다음과 같다
영준: [1B 1C 5A 5C 6A 6B 6C 6D 7A 7B 7C 7D 9A 9C 10A 10B 10C 10D 11A 11B 11C 11D 12B 12C]
라미: [1A 1D 2A 2B 2C 2D 3A 3B 3C 3D 4A 4B 4C 4D 5B 5D 8A 8B 8C 8D 9B 9D 12A 12D]
최종 점수는,
영준이는 멍따 5개 = 1점, 띠 10개 = 1점, 피점수 13개 = 4점, 총점 6점.
라미는 광점수 4개 = 4점, 고도리 5점, 띠점수 5개 = 1점, 피점수 12개 = 3점, 총점 13점으로 라미가 승리하였다.

출처/분류