Rtetris

너비 6, 높이 7인 고정된 구덩이와 최대 200개의 테트리스 조각 순서가 주어질 때, 빈칸이 생기지 않도록 모든 조각을 놓을 수 있는지 판정하고 지운 줄 수의 최댓값을 구한다.

어려움8동적 계획법시뮬레이션비트 연산아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

Rtetris는 테트리스의 옛 변종이다. 규칙이 지금보다 훨씬 가혹해서, 최상위 선수들은 손에 든 조각을 미리 전부 읽고 한 판의 수순을 통째로 짜 주는 보조 프로그램으로 부정을 저질렀다. 그 보조 프로그램을 다시 만든다.

판은 너비 WW, 높이 HH의 정수 격자다. 한 판에 쓰는 조각은 NN개이고, 손패와 그 순서는 시작 전에 모두 공개된다. 조각은 모두 단위 정사각형 네 칸으로 이루어지며 일곱 종류가 있다. 각각 1부터 7까지의 숫자로 나타낸다.

1     2     3     4     5     6     7

##    .#.   .##   ##.   #..   ..#   ####
##    ###   ##.   .##   ###   ###

각 그림에서 아래쪽 줄이 조각의 밑면이다.

한 수는 다음 순서로 진행한다.

  1. 손패의 다음 조각을 판 위에 든다. 떨어뜨리기 전에 90도 단위로 회전하고 좌우로 옮길 수 있다. 회전한 뒤에도 조각 전체가 판의 너비 안에 들어와야 한다.
  2. 조각은 바닥이나 이미 쌓인 블록에 닿을 때까지 수직으로 내려간다.
  3. 멈춘 조각의 칸이 하나라도 판의 위쪽 경계를 넘으면 그 자리에서 진다.
  4. 조각은 네 칸으로 흩어져 판에 합쳐진다. 완전히 채워진 가로줄은 모두 동시에 사라지고, 그 위의 블록은 아래에서 사라진 줄 수만큼 내려온다.
  5. 줄이 사라진 뒤에는 어느 세로줄에도 빈틈이 없어야 한다. 즉 각 세로줄에서 채워진 칸은 바닥부터 끊기지 않고 이어져야 한다. 빈 칸 위에 블록이 있는 세로줄이 하나라도 있으면 그 자리에서 진다.

빈틈 검사는 줄이 사라진 뒤에 한다. 그래서 떨어뜨리는 순간에는 빈틈이 남을 것처럼 보여도, 그 수로 줄이 채워져 사라진다면 정당한 수다.

NN개를 모두 놓을 때까지 지지 않으면 이긴다. 첫 조각이 3이면 빈 판의 어디에 놓아도 빈틈이 생기므로 그 판은 바로 진다.

각 판마다 이길 수 있는지 판정하고, 이길 수 있다면 사라진 줄이 가장 많은 진행에서 몇 줄이 사라지는지 구한다.

입력

여러 판이 이어서 주어진다. 각 판은 공백으로 구분된 정수 세 개 NN, WW, HH가 있는 줄로 시작한다. NN은 손패의 크기로 1N2001 \le N \le 200이다. WW는 판의 너비, HH는 판의 높이다. 팀이 심판을 매수해 둔 덕분에 WW는 항상 6, HH는 항상 7임을 알고 있다.

다음 줄에는 손패의 조각 NN개가 놓는 순서대로 주어진다. 각 조각은 1부터 7까지의 숫자 하나이고 공백으로 구분한다.

입력의 끝은 0 0 0만 있는 줄로 표시한다.

출력

판마다 한 줄씩 출력한다. 손패를 전부 놓는 진행이 없으면 Game cannot be won을 출력한다. 그렇지 않으면 Game can be won with X lines removed를 출력한다. 여기서 XX는 이기는 진행 가운데 사라진 줄 수의 최댓값이다. XX가 0이거나 1일 때도 같은 문장을 그대로 쓴다.