테트리스

NYPC 2017 · 본선

테트리스 초고수 배찌는 간식을 걸고 테트리스 내기를 해서 다른 캐릭터의 간식을 뺏어먹는 것이 특기이다. 악명 높은 배찌의 간식 내기를 무서워하는 다른 캐릭터들은 배찌를 막기 위해 테트리스 매크로를 만들기로 결심했다.

테트리스는 44개의 격자로 구성된 블록들과, 20×1020 \times 10 크기의 격자판으로 하는 간단하고 유명한 퍼즐 게임이다. 규칙은 다음과 같다.

테트리스 배틀을 이기기 위해서는 최대 콤보가 높아야 한다. 콤보는 다음과 같이 계산된다.

배찌에게 간식을 뺏긴 캐릭터들은 힘을 합쳐 매크로를 만들어보려고 했지만, 아무리 해도 높은 콤보를 내는 매크로는 만들 수 없었다. 캐릭터들을 도와 떨어지는 블록의 순서가 주어졌을 때 높은 콤보를 내는 방법을 찾는 프로그램을 작성해주자.

입력 형식

입력은 여러 번의 게임으로 이루어진다.

첫 번째 줄에 게임의 횟수 TT가 주어진다. (1T101 \le T \le 10)

각 게임의 첫 번째 줄에 블록의 개수 NN이 주어진다. (1N1001 \le N \le 100)

두 번째 줄에 블록이 떨어지는 순서를 나타내는 NN개의 블록 번호가 주어진다. 블록 번호는 위의 그림에서, 빨간색 블록부터 보라색 블록까지 순서대로 00부터 66까지의 자연수로 배정된다.

채점에 사용되는 입력데이터는 블록들을 무작위로 생성한 것임이 보장된다.

출력 형식

각 테스트케이스 별로 N+max(0,(홀드 횟수)1)N+\max(0, (\textrm{홀드 횟수})-1)개의 줄에 각 턴에 하는 행동을 출력한다. 홀드 기능을 사용한 경우 HH를, 사용하지 않은 경우 회전 횟수 rr과 떨어지는 블록의 가장 왼쪽 위치 xx를 공백을 사이에 두고 출력한다. (0r30 \le r \le 3, 0x90 \le x \le 9)

격자칸의 가장 왼쪽 위치는 00이며, 가장 오른쪽 위치는 99이다. 블록 회전은 시계 방향으로 9090도 회전시키는 것을 의미한다.

예제

입력

1 7 0 1 0 0 0 1 0

출력

0 0 H 0 4 0 2 0 6 H 0 0 H 0 8

예제 설명

예제 출력은 22콤보이며, 77번째 줄에서 11번 블록으로, 99번째 줄에서 11번 블록으로 각각 한 줄을 제거하였다.

채점 방식

각 테스트케이스의 점수는 아래와 같이 계산된다.

최종 점수는 모든 테스트케이스 점수의 합이다.

해설