너비 6, 높이 7인 고정된 구덩이와 최대 200개의 테트리스 조각 순서가 주어질 때, 빈칸이 생기지 않도록 모든 조각을 놓을 수 있는지 판정하고 지운 줄 수의 최댓값을 구한다.
어려움8동적 계획법시뮬레이션비트 연산아직 제출이 없습니다시간 제한2초메모리 제한512 MBRtetris는 테트리스의 옛 변종이다. 규칙이 지금보다 훨씬 가혹해서, 최상위 선수들은 손에 든 조각을 미리 전부 읽고 한 판의 수순을 통째로 짜 주는 보조 프로그램으로 부정을 저질렀다. 그 보조 프로그램을 다시 만든다.
판은 너비 W, 높이 H의 정수 격자다. 한 판에 쓰는 조각은 N개이고, 손패와 그 순서는 시작 전에 모두 공개된다. 조각은 모두 단위 정사각형 네 칸으로 이루어지며 일곱 종류가 있다. 각각 1부터 7까지의 숫자로 나타낸다.
1 2 3 4 5 6 7
## .#. .## ##. #.. ..# ####
## ### ##. .## ### ###
각 그림에서 아래쪽 줄이 조각의 밑면이다.
한 수는 다음 순서로 진행한다.
빈틈 검사는 줄이 사라진 뒤에 한다. 그래서 떨어뜨리는 순간에는 빈틈이 남을 것처럼 보여도, 그 수로 줄이 채워져 사라진다면 정당한 수다.
N개를 모두 놓을 때까지 지지 않으면 이긴다. 첫 조각이 3이면 빈 판의 어디에 놓아도 빈틈이 생기므로 그 판은 바로 진다.
각 판마다 이길 수 있는지 판정하고, 이길 수 있다면 사라진 줄이 가장 많은 진행에서 몇 줄이 사라지는지 구한다.
여러 판이 이어서 주어진다. 각 판은 공백으로 구분된 정수 세 개 N, W, H가 있는 줄로 시작한다. N은 손패의 크기로 1≤N≤200이다. W는 판의 너비, H는 판의 높이다. 팀이 심판을 매수해 둔 덕분에 W는 항상 6, H는 항상 7임을 알고 있다.
다음 줄에는 손패의 조각 N개가 놓는 순서대로 주어진다. 각 조각은 1부터 7까지의 숫자 하나이고 공백으로 구분한다.
입력의 끝은 0 0 0만 있는 줄로 표시한다.
판마다 한 줄씩 출력한다. 손패를 전부 놓는 진행이 없으면 Game cannot be won을 출력한다. 그렇지 않으면 Game can be won with X lines removed를 출력한다. 여기서 X는 이기는 진행 가운데 사라진 줄 수의 최댓값이다. X가 0이거나 1일 때도 같은 문장을 그대로 쓴다.