도장

이 문제는 휴리스틱 최적화 문제이다.

색칠된 $N\times N$ 격자 $A$, $D\times D$ 도장 $S$, 목표 그림 $T$가 주어진다. 색은 $0$부터 $C-1$까지의 정수이다. $0$도 다른 색과 동일하게 취급한다.

좌표는 모두 $0$부터 시작한다. 왼쪽 위 칸은 $(0,0)$이다. 아래로 갈수록 행 번호가, 오른쪽으로 갈수록 열 번호가 증가한다.

한 번의 작업으로 다음을 수행한다.

• $D\times D$ 영역의 왼쪽 위 좌표 $(x,y)$와 $r\in\{0,1,2,3\}$을 선택한다.

도장은 격자 밖으로 나가면 안 된다. 같은 영역에 다시 찍거나 이전 영역과 겹쳐도 된다. 이동과 회전에는 별도의 작업 횟수가 들지 않는다. 매 작업의 회전은 기준 방향에 대한 값이며 누적하지 않는다.

도장의 칸 $(u,v)$가 놓이는 영역 내부의 좌표 $R_r(u,v)$는 다음과 같다.

$R_r(u,v)=(p,q)$인 모든 칸에 대해 $S_{u,v}$와 를 교환한다.

작업을 최대 $K$번 수행하여 최종 격자에서 목표 $T$와 색이 같은 칸을 가능한 한 많이 만들어라. 목표 그림은 바뀌지 않는다. 중간 상태와 마지막 도장의 색은 점수에 포함하지 않는다. 작업을 하지 않아도 된다. 모든 칸을 맞출 수 있다는 보장은 없다.

점수

최종적으로 일치하는 칸 수가 $M$이면 해당 입력의 점수는 $P=\left\lfloor 10^6M/N^2\right\rfloor$이다. 40개 평가 입력의 점수를 합하며 최대 총점은 $40$점이다. 잘못된 출력이나 실행 제한 초과가 발생한 입력만 점으로 처리한다. 점수는 다른 참가자나 기준 풀이에 의존하지 않는다. 총점이 같으면 공동 순위이다.

재생기 도장 재생기 열기

하나의 입력 파일에는 하나의 문제가 다음 형식으로 주어진다.

$N\ D\ C\ K$ $A_{0,0}\ A_{0,1}\ \cdots\ A_{0,N-1}$

작업 수 $L$과 각 작업의 $x_i,y_i,r_i$를 순서대로 출력한다.

• $3\le N\le30$.
• $D\in\{2,3\}$, $D\le N$.