Tiny - 4

옛날 사람들은 Alexey Pajitnov가 만든 유명한 컴퓨터 게임 "TETRIS"를 아직도 기억한다. 이 게임에서는 정사각형 네 개로 이루어진 조각(테트로미노)이 하늘에서 떨어지고, 플레이어는 조각을 회전시켜 직사각형 통에 내려놓는다. 목표는 빈틈없이 블록이 채워진 줄을 가능한 한 많이 만드는 것이다. 줄이 완성되면 그 줄은 사라지고, 뒤따르는 조각이 놓일 공간이 생긴다.

이번에는 더 단순한 버전인 "Tiny TETRIS"(줄여서 "Tiny")를 살펴보자. Tiny 조각(t-piece)은 정사각형 한 개에서 세 개로 이루어진 것이 모두 아홉 종류뿐이다:

조각 위의 숫자는 t-piece의 종류를 나타내며, 이후 특정 t-piece를 가리킬 때 이 번호를 쓴다.

게임의 목표도 같다. 떨어지는 t-piece를 가로 9칸, 세로 9칸인 직사각형 통에 넣어야 한다. TETRIS와 달리 t-piece는 회전할 수 없다. 떨어지기 시작한 뒤에는 좌우로 움직일 수도 없다. 따라서 플레이어는 각 t-piece마다 가장 왼쪽 칸(×로 표시)이 떨어질 열 번호(1부터 9까지의 정수)만 고른다.

한 게임은 길이가 N인 유한한 t-piece 순서로 이루어진다. 통의 위쪽을 넘지 않고 불법적인 이동도 하지 않으면서 가능한 한 많은 t-piece를 통에 떨어뜨려야 한다. 게임의 점수는 성공적으로 떨어뜨린 t-piece의 개수와 같다.

게임을 시작할 때 게임 카운터는 0으로 설정된다.

게임의 진행 순서는 다음과 같다.

1. 플레이어가 현재 t-piece의 가장 왼쪽 칸이 떨어질 열을 고른다.
2. 열이 올바르게 설정되면 t-piece는 장애물에 닿을 때까지 아래로 떨어진다. 그렇지 않으면 게임이 끝난다.
3. t-piece가 모든 칸까지 통 안에 완전히 들어가면(즉, 모든 칸이 9×9 직사각형 안에 있으면) 카운터 값을 1 올린다. 그렇지 않으면 게임이 끝난다.
4. 그다음 완성된 가로줄이 있는지 확인한다. 빈틈없이 t-piece 블록으로 가득 찬 가로줄이 완성된 줄이다. 완성된 줄이 있으면 그 줄은 사라지고, 그 위의 줄들은 배열을 바꾸지 않은 채 아래로 내려온다.
5. 남은 t-piece가 있으면 1)로 돌아간다. 없으면 게임이 끝난다.

특정 게임의 점수는 게임이 끝나는 순간의 카운터 값이다.

한 게임을 자세히 분석해 보자.

주어진 t-piece 20개의 순서는 5,4,1,6,7,6,4,4,7,9,5,5,6,8,3,4,3,7,4,2이다. 처음 17개의 t-piece는 열 1,2,2,4,8,8,7,4,8,6,1,1,4,8,3,7,7에 차례로 성공적으로 떨어졌다고 하자. 지금까지 완성된 줄은 없고 카운터 값은 17이다. 이제 t-piece 7을 떨어뜨릴 차례다(그림의 문자는 t-piece에 순서대로 붙인 것이다):

t-piece 7을 떨어뜨릴 수 있는 열은 두 곳뿐이다:

a) 열 1:	b) 열 5(이 경우 한 줄이 완성되어 사라진다):

각각 특정 게임을 설명하는 파일 다섯 개가 주어진다. tiny.i01, tiny.i02, tiny.i03, tiny.i04, tiny.i05가 그것이다. 각 파일은 t-piece의 순서를 담고 있으며 다음 형식을 따른다. 첫 줄에는 정수 N이 하나 있다. 다음 N줄은 t-piece의 순서를 나타내며, 각 줄에는 1부터 9 사이의 정수 하나가 있다. 이것이 해당 t-piece의 번호다. t-piece는 통에 떨어뜨려야 하는 순서대로 주어지며, i번째 t-piece는 파일의 i+1번째 줄에 있다.

주어진 입력 파일마다 그에 대응하는 출력 파일을 제출해야 한다. 출력 파일은 최대 N줄이며, 각 줄에는 조각을 떨어뜨린 열 번호가 있다. 출력 파일의 i번째 줄에는 입력의 i번째 t-piece를 떨어뜨릴 열 번호가 있어야 한다.

각 입력 파일에 대해, 모든 t-piece를 통에 성공적으로 떨어뜨릴 수 있는 열의 순서가 존재함이 보장된다(그 게임의 최종 점수가 N이 되는 열의 순서가 존재한다).