색종이

NYPC 2018 · 본선

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

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

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

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

입력 형식

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

다음 NN개의 줄에는 11이상 CC이하의 정수 MM개가 공백으로 구분되어 주어진다. ii번째 줄의 jj번째 수는 원하는 그림의 (i,j)(i, j)번 격자의 색을 의미한다.

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

출력 형식

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

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

입력 데이터 및 생성 방법

1010개의 입력 데이터는 다음의 NN, MM, CC, VV가 주어진다.

#NNMMCCVV
11113030221010
22113030331313
3355552288
445555331111
5530303030222020
6630303030332020
773030303022450450
773030303022450450
993030303022225225
10103030303033300300

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

VV는, 11, 22, 33, 44번 데이터의 경우에는 최소의 가능한 색종이 개수 +1+1로, 55번, 66번의 경우 데이터를 만들 때 사용한 직사각형의 갯수로, 77번, 88번의 경우 NM(C1)C\displaystyle\frac{NM(C-1)}{C}로, 99번, 1010번의 경우에는 NM(C1)2C\displaystyle\frac{NM(C-1)}{2C}로 결정되었다.

배점

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

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

T<VT < V이면 1010점, VTNMV \le T \le NM 이면, T=VT = V일때 1010점, T=NMT = NM 일때 11점을 기준으로 점수가 선형으로 주어진다. 즉, 점수는

1+9×NMTNMV1 + 9 \times \frac{NM-T}{NM-V}

이다. 그 후, 각 테스트케이스의 점수는 0.050.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=3N = 3, M=3M = 3, T=5T = 5이기 때문에, 해당하는 점수는 1+9×9593=71 + 9 \times \displaystyle\frac{9-5}{9-3} = 7점이다.

채점 방식

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

해설