27904번 - 키파-틱택토 서브태스크스페셜 저지

문제

틱택토는 두 명이 번갈아가며 O와 X를 3×3 판에 써서 같은 글자를 가로, 세로, 혹은 대각선 상에 놓이도록 하는 놀이입니다.^[1] 틱택토는 상대적으로 단순한 전략 놀이로, 몇 번 해 보면 양쪽이 최선을 다하는 경우 비긴다는 사실을 알 수 있습니다.

키파는 틱택토가 너무 단순한 놀이라고 생각해서, 틱택토를 더욱 확장한 키파-틱택토를 만들었습니다. 키파-틱택토는 유비트의 판 모양과 비슷한 4×4 판에서 진행하며, X부터 시작하여 번갈아 가며 판을 한 칸씩 채웁니다. 각 칸을 아래와 같이 부르겠습니다.

키파는 틱택토의 승리 조건도 너무 단순하다고 생각했고, 비기는 경우가 있는 것도 마음에 안 들어서, 승리 조건 역시 바꾸었습니다. 일단 판을 모두 채워 X가 여덟 개, O가 여덟 개 있는 상황에서, 아래와 같은 승리 조건에 따라 승자를 결정합니다.

[フレーム]

플레이어는 놀이 중 차례에 상관없이 승리를 선언할 수 있습니다. 현재 열여섯 칸이 모두 채워지지 않았지만, 이 상태에서 게임이 규칙에 따라 어떻게 진행되더라도 최종적으로 승리 조건에 따라 이기는 사람이 한 사람으로 정해져 있을 수 있습니다. 이 경우 그 사람은 승리 선언 조건을 만족합니다. 플레이어가 승리 선언 조건을 만족한 상태에서 승리를 선언하면 놀이에서 곧바로 이깁니다. 열여섯 칸이 모두 채워진 경우 승리를 선언할 수 없음에 유의하세요.

이 놀이를 완벽하게 익힌 키파와 아바나가 키파-틱택토를 합니다. 키파는 아바나에게 선을 양보했습니다. 놀이가 이미 어느 정도 진행되었고, 여기서부터 양쪽이 최선을 다하는 경우 키파-틱택토가 어떻게 진행되는지를 계산하는 프로그램을 작성하세요.

입력

첫째 줄에 테스트 케이스의 수 T가 주어집니다. T는 1 이상 300 000 이하입니다.

각 테스트 케이스는 총 네 줄로 이루어져 있습니다. 각 줄에는 정확히 네 개의 문자로 이루어진 문자열이 주어집니다. 각 문자는 O, X 또는 . 중 하나이며, 테스트 케이스의 i행에 주어진 문자열의 j번째 문자가 O나 X인 경우 i행 j열에 그 문자가 그려져 있음을, .인 경우 아무 것도 그려져 있지 않음을 의미합니다.

모든 테스트 케이스는 빈 판에서 올바르게 놀이를 진행한 상태입니다. 즉, 열여섯 개의 문자 중 X의 개수에서 O의 개수를 뺀 값을 D라 하면, D가 0인 경우는 현재 X의 차례, D가 1인 경우는 현재 O의 차례이며, 이외의 경우는 입력으로 주어지지 않습니다.

출력

각각의 테스트 케이스에 대해, KIPA WINS, HAVANA WINS, KIPA DECLARES A WIN, HAVANA DECLARES A WIN 중 하나를 한 줄에 출력합니다.

제한

채점 규칙

서브태스크에 특별한 제약이 없다면, 각 테스트 케이스가 맞은 것으로 인정되기 위해서는 다음의 규칙을 따라야 합니다.

• 현재 상태에서 키파가 승리를 선언하여 승리할 수 있는 경우 KIPA DECLARES A WIN을 출력해야 합니다.
• 현재 상태에서 아바나가 승리를 선언하여 승리할 수 있는 경우 HAVANA DECLARES A WIN을 출력해야 합니다.
• 그렇지 않고 계속 진행해야 하는 경우, 키파와 아바나가 모두 최선을 다했을 때, 키파가 이긴다면 KIPA WINS를, 아바나가 이긴다면 HAVANA WINS를 출력해야 합니다.

서브태스크 1 (2점)

이 서브태스크의 모든 테스트 케이스의 입력에서 X는 1행 1열, 2행 3열과 4행 1열 세 개에만 주어지며, D = 1입니다.

더불어 이 서브태스크에서는 각 테스트 케이스의 채점을 다음과 같은 방식으로 진행합니다.

1. 정답과 출력의 첫째 단어가 일치하는지 확인합니다. 불일치하면 틀렸습니다를 받습니다.
2. 일치하면 이 테스트 케이스에 대해서는 맞은 것으로 처리됩니다.

예를 들어, 정답이 HAVANA DECLARES A WIN이고, HAVANA WINS를 출력한 경우 이 서브태스크에서는 정답으로 인정됩니다.

[출력 조건]은 여전히 지켜야 함에 유의하세요. 정답이 KIPA WINS일 때 KIPA IS CUTE를 출력하더라도 🥰 정답으로 인정되지 않습니다. 😢

서브태스크 2 (8369점)

이 서브태스크의 입력에는 .이 없습니다. 채점 방식은 출력 란의 [채점 규칙]을 따릅니다.

서브태스크 3 (5581점)

이 서브태스크에서는 T ≤ 50 000입니다.

더불어 이 서브태스크에서는 각 테스트 케이스의 채점을 다음과 같은 방식으로 진행합니다.

1. 먼저 정답과 출력의 둘째 단어가 일치하는지 확인합니다. 불일치하면 틀렸습니다를 받습니다.
2. 일치한다면, 정답의 둘째 단어가 WINS인지 확인합니다. 그렇다면 이 테스트 케이스는 맞은 것으로 처리됩니다.
3. 그렇지 않다면, 정답과 출력의 첫째 단어가 일치하는지 확인합니다. 그렇다면 이 테스트 케이스는 맞은 것으로 처리되고, 그렇지 않으면 틀렸습니다를 받습니다.

예를 들어, 정답이 HAVANA WINS이고, KIPA WINS를 출력한 경우 이 서브태스크에서는 정답으로 인정됩니다.

서브태스크 1과 마찬가지로 [출력 조건]은 여전히 지켜야 합니다. 정답이 KIPA WINS일 때 KIPA WINS A MILLION DOLLAR를 출력하더라도 🤑 정답으로 인정되지 않습니다. 😠

서브태스크 4 (11161점)

추가적인 제약 조건이 없습니다. 채점 방식은 출력 란의 [채점 규칙]을 따릅니다.

서브태스크 5 (2791점)

추가적인 제약 조건이 없습니다. 이 서브태스크에서는 각 테스트 케이스의 채점은 [채점 규칙]을 따르나, 규칙에 따라 모든 테스트 케이스가 맞은 것으로 처리된 경우 다음과 같은 방식에 따라 최종 채점 결과를 결정합니다.

1. 소스 코드의 길이가 2 023바이트를 넘으면 틀렸습니다를 받습니다.
2. 아니라면 맞았습니다!!를 받습니다.

힌트