스누커

사진 출처: 플리커

Arnar는 최근 스누커를 보고 있다. 스누커는 커다란 직사각형 테이블에서 진행되며, 선수들은 맞춤 제작된 막대기인 큐를 사용한다. 테이블의 경기 구역은 길이가 $140.5$인치이고 너비가 $70$인치이다. 테이블에는 여섯 개의 포켓이 있는데, 각 모서리에 하나씩 있고 나머지 두 개는 긴 변 각각의 중앙에 있다.

테이블 위에는 여러 색깔의 공도 있으며, 각 색깔에는 용도가 있다. 각 공의 반지름은 $1$인치이다. 색깔은 빨간색, 노란색, 초록색, 갈색, 파란색, 분홍색, 검은색이다. 또한 테이블 위에는 선수들이 큐로 칠 수 있는 유일한 공인 흰색 공이 있다. 선수들은 큐의 한쪽 끝으로 흰색 공을 찔러 테이블 위에서 굴러가게 한다. 흰색 공은 테이블의 변에 부딪혀 튕길 수 있으며, 다른 공들과 충돌할 수도 있다. 게임의 목표는 흰색 공으로 색깔 공을 쳐서 테이블의 포켓에 들어가도록 하는 것이며, 이를 공을 포켓에 넣는다고 한다. 공을 포켓에 넣으면 색깔에 따라 점수를 얻으며, 이는 다음 표에서 확인할 수 있다.

색깔      |  점수

빨간색    |  $1$

노란색    |  $2$

초록색    |  $3$

갈색      |  $4$

파란색    |  $5$

분홍색    |  $6$

검은색    |  $7$

흰색 공을 칠 때마다, 흰색 공으로 가장 먼저 맞혀야 할 특정 색깔이 지정되며 이를 온 색깔이라고 한다. 선수가 올바른 색깔의 공을 포켓에 넣을 때마다 그 선수는 흰색 공을 다시 칠 수 있다. 선수가 자신의 차례를 시작할 때 테이블 위에 빨간색 공이 있다면 빨간색이 온 색깔이다. 선수가 빨간색 공을 포켓에 넣으면 다음 샷의 온 색깔을 빨간색을 제외하고 선택할 수 있다. 선수가 그 샷에서 색깔 공을 포켓에 넣으면, 점수가 부여된 뒤 그 색깔 공을 테이블 위에 다시 놓는다. 그 샷이 끝나면 온 색깔은 다시 빨간색으로 설정된다.

흰색 공이 올바른 색깔의 공을 가장 먼저 맞히면 그 샷은 HIT이다. 흰색 공이 잘못된 색깔의 공을 가장 먼저 맞히면 그 샷은 FOUL이다. 흰색 공이 어떤 공도 맞히지 않으면 그 샷은 MISS이다. 흰색 공은 공을 맞히기 전과 후 모두 테이블의 변을 가능한 한 여러 번 맞힐 수 있음에 유의한다.

게임의 목표 중 하나는 흰색 공을 상대가 치기 어려운 위치에 놓이도록 쳐서 상대를 스누커 상태로 만드는 것이다. 이때 올바른 공을 맞히기 어려울 수 있으며, 직선으로 직접 치는 샷이 불가능할 수도 있다. 그러면 보통 흰색 공이 공을 맞히기 전에 테이블의 변에서 튕기도록 친다. 튕기는 경로를 시각화하기 어려울 수 있으므로, Arnar는 흰색 공이 올바른 공을 맞히는지 알려 주기를 원한다.

테이블의 현재 상태, 온 색깔, 그리고 큐로 친 뒤 흰색 공이 이동할 경로에 대한 설명이 주어진다. 그 샷이 HIT, FOUL, 또는 MISS인지 판별한다. 문제를 단순화하기 위해 테이블에 포켓이 없다고 가정해도 되므로, 흰색 공은 포켓에 들어갈 수 없고 테이블의 변에 부딪힐 때마다 항상 튕긴다.

채점

그룹 | 점수 | 제한

1 | 30 | 흰색 공은 테이블의 변에 닿을 만큼 멀리 이동하지 않는다. $v_x = 0$ 또는 $v_y = 0$ 중 하나이다.

2 | 20 | $v_x = 0$ 또는 $v_y = 0$ 중 하나이다.

3 | 25 | 흰색 공은 테이블의 변에 닿을 만큼 멀리 이동하지 않는다.

4 | 25 | 추가 제한이 없다.

입력의 첫째 줄에는 테이블 위의 공 개수를 나타내는 하나의 정수 $n$이 주어지며, $2 \leq n \leq 22$이다. 이어서 $n$개의 줄이 주어진다. 각 줄에는 공의 색깔과 두 실수 $x_i$가 주어진다. 이때 $1 \leq x_i \leq 69$이고, $y_i$가 주어진다. 이때 $1 \leq y_i \leq 139.5$이며, 이들은 $i$번째 공의 위치를 나타낸다. 그다음 줄에는 온 색깔이 주어진다. 마지막으로 입력은 공백으로 구분된 두 실수 $v_x$와 $v_y$로 이루어진 줄로 끝난다. 이때 $-1\,000 \leq v_x, v_y \leq 1\,000$이며, 이들은 각 축에서 흰색 공이 이동할 거리를 나타낸다.

공의 색깔은 문자열 white, red, yellow, green, brown, blue, pink, black로 나타낸다. 테이블 위에는 빨간색 공이 최대 $15$개 있을 수 있지만, 다른 각 색깔의 공은 최대 $1$개만 있을 수 있다. 흰색 공은 항상 테이블 위에 있으며, 온 색깔과 같은 색깔의 공도 적어도 하나는 항상 테이블 위에 있다. 각 공의 위치는 테이블의 왼쪽 위 모서리에서 공의 중심까지의 거리를 인치 단위로 나타내어 주어진다. 따라서 왼쪽 위 모서리의 위치는 $(0, 0)$이고 오른쪽 아래 모서리의 위치는 $(70, 140.5)$이다. 공들은 서로 겹치지 않지만 서로 맞닿을 수 있다고 가정해도 된다. 단, 흰색 공은 처음에 어떤 공과도 맞닿아 있지 않는다. 모든 실수는 소수점 아래 정확히 세 자리까지 주어진다.

흰색 공이 올바른 색깔의 공을 가장 먼저 맞히면 HIT을 출력하고, 흰색 공이 잘못된 색깔의 공을 가장 먼저 맞히면 FOUL을 출력하며, 흰색 공이 어떤 공도 맞히지 않으면 MISS을 출력한다. 공의 위치가 $10^{-3}$인치 미만으로 변해도 답은 바뀌지 않으며, 따라서 답이 모호한 경우는 없다고 가정해도 된다.

첫 번째 예제는 그룹 $1$에 속한다. 흰색 공이 검은색 공을 가장 먼저 맞히므로 답은 HIT이다.

[ht!]

예제 1

두 번째 예제는 그룹 $2$에 속한다. 흰색 공은 아래쪽 변에서 튕긴 다음 테이블 위쪽으로 이동한다. 흰색 공이 분홍색 공을 가장 먼저 맞히므로 답은 FOUL이다.

[ht!]

예제 2

세 번째 예제는 그룹 $3$에 속한다. 흰색 공은 초록색 공과 갈색 공 사이를 지나간다. 흰색 공이 파란색 공을 가장 먼저 맞히므로 답은 FOUL이다.

[ht!]

예제 3

네 번째 예제는 그룹 $4$에 속한다. 흰색 공은 먼저 갈색 공과 노란색 공 사이를 지나간 뒤, 아래쪽 변에서 튕기고 이어서 왼쪽 변에서 튕긴다. 그다음 흰색 공은 초록색 공을 지나치고 위쪽 변에서 튕긴 뒤, 초록색 공과 갈색 공 사이를 지나간다. 마지막으로 흰색 공은 아래쪽 변에서 튕긴 뒤 오른쪽 변 근처에서 멈춘다. 흰색 공이 멈추기 전에 어떤 공도 맞히지 않았으므로 답은 MISS이다.

[ht!]

예제 4