색종이

$N\times M$ 크기의 격자 모양의 스케치북과 다양한 크기의 색종이들을 가지고 있다. 위에서 부터 $i$번째 행, 왼쪽에서 부터 $j$번째 열에 해당하는 격자는 $(i, j)$번 격자라고 부른다. 예를 들어, 가장 왼쪽 위의 격자는 $(1, 1)$, 오른쪽 아래의 격자는 $(N, M)$ 번 격자다.

당신에겐 크기와 색을 마음대로 정할 수 있는 색종이가 $NM$개 주어진다. 색종이의 색은 $1$이상 $3$이하의 정수로 표현된다.

이 스케치북에 격자에 맞는 색종이들을 스케치북에 잘 붙여서 원하는 그림의 모양을 만들고자 한다. 각 격자의 색상은 마지막에 붙인 색종이의 색상이 된다. 단, 각 격자에 붙어있는 색종이가 반드시 있도록 붙여야한다.

색종이들을 적게 사용해서 원하는 그림을 만드는 방법을 구하여라.

입력 형식

첫째 줄에는 세로의 길이 $N$, 가로의 길이 $M$, 사용할 수 있는 색종이의 개수 $V$가 공백으로 구분되어 주어진다.

다음 $N$개의 줄에는 $1$이상 $C$이하의 정수 $M$개가 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 수는 원하는 그림의 $(i, j)$번 격자의 색을 의미한다.

$C$는 별도로 입력으로 주어지지 않는다. $C$에 관련해서는 아래 입력 데이터 및 생성 방법을 참고하자.

출력 형식

첫째 줄에 사용한 색종이의 개수 $T$를 출력한다.

다음 $T$개의 줄에는 색종이를 붙인 순서대로 색종이에 대한 정보를 줄로 구분하여 출력한다. 색종이의 정보는 $x$, $y$, $z$, $w$, $c$를 차례로 공백으로 구분하여 출력한다. 이는 사용한 색종이의 왼쪽 위 격자가 $(x, y)$, 오른쪽 아래 격자가 $(z, w)$, 색이 $c$라는 것을 의미한다. ($1 \le x \le z \le N$, $1 \le y \le w \le M$, $1 \le c \le 3$ 를 만족하게 출력해야 한다.)

입력 데이터 및 생성 방법

$10$개의 입력 데이터는 다음의 $N$, $M$, $C$, $V$가 주어진다.

$5$, $6$번 데이터를 제외하고는, 각 칸을 $1$이상 $C$이하의 수를 랜덤으로 정하여 생성되었다. $5$, $6$번 데이터는 첫번째 직사각형으로 전체를 덮은 후, 직사각형 $V-1$개를 랜덤하게 생성하여 덮는 방법으로 생성되었다.

$V$는, $1$, $2$, $3$, $4$번 데이터의 경우에는 최소의 가능한 색종이 개수 $+1$로, $5$번, $6$번의 경우 데이터를 만들 때 사용한 직사각형의 갯수로, $7$번, $8$번의 경우 $\displaystyle\frac{NM(C-1)}{C}$로, $9$번, $10$번의 경우에는 $\displaystyle\frac{NM(C-1)}{2C}$로 결정되었다.

배점

배점은 각 테스트 데이터당 $10$점이다.

$T > NM$ 혹은, 색종이를 붙였을 때 그림이 일치하지 않으면, $0$점을 받는다.

$T < V$이면 $10$점, $V \le T \le NM$ 이면, $T = V$일때 $10$점, $T = NM$ 일때 $1$점을 기준으로 점수가 선형으로 주어진다. 즉, 점수는

이다. 그 후, 각 테스트케이스의 점수는 $0.05$ 단위로 버림된다.

예제

3 3 3
2 2 2
2 1 2
2 1 2

5
1 1 2 2 3
2 3 3 3 1
1 1 2 3 2
2 1 3 3 2
2 2 3 2 1

예제 설명

이 출력에서는 5개의 색종이를 사용해서 그림을 만들었다. 그림이 일치하고, $N = 3$, $M = 3$, $T = 5$이기 때문에, 해당하는 점수는 $1 + 9 \times \displaystyle\frac{9-5}{9-3} = 7$점이다.

채점 방식

이 문제는 풀이 소스코드를 제출하지 않고, 각 테스트케이스의 입력데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

해설