VM 10 Bài 03 - Tô màu

View as PDF

Submit solution

Points: 2.00 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VM10 - Tác giả: Khúc Anh Tuấn
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Tèo được các admin VNOI đố cho một trò chơi như sau:

  • Tèo có một bảng hình chữ nhật ~N \times M~, mỗi ô có một màu nhất định và ~K~ lần tô màu.
  • Trong mỗi lần tô màu, Tèo chọn một vùng có số hiệu màu như nhau và tô một màu khác. (Một vùng là một dãy các ô chung cạnh có cùng màu với nhau).

Ví dụ:

image

Ở hình bên trái nếu ta chọn ô ~(3~, ~3)~ màu xanh lá và tô thành màu vàng thì sẽ thu được hình bên phải.

Sau khi biến đổi, bảng màu sẽ có ~Q~ vùng, mỗi vùng sẽ có ~c_{i}~ ô ~(i = 1 \rightarrow Q)~. Câu hỏi của các admin VNOI cho Tèo là: Hãy chỉ ra cách tô màu sau ~K~ lần sao cho ~c_{1}^2 + \dots + c_{Q}^2~ càng lớn càng tốt.

Input

  • Dòng đầu tiên chứa ~3~ số ~n~, ~m~, ~k~. ~(n~, ~m~, ~k \leq 50)~
  • ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số thể hiện màu được tô cho ô tương ứng trên bảng (mỗi màu khác nhau được đánh một số hiệu khác nhau và các ô có màu giống nhau thì được đánh cùng một số). Số hiệu màu là số tự nhiên không vượt quá ~3000~.

Output

  • Ghi ra trên ~k~ dòng, thể hiện các bước tô màu theo thứ tự tăng dần của thời gian, mỗi dòng có dạng: ~i~, ~j~, ~t~ tương ứng với việc tô màu ~t~ cho ô ~(i~, ~j)~.

Giới hạn

  • Điểm cho mỗi output hợp lệ sẽ tỷ lệ với tổng ~c_{1}^2 + \dots + c_{Q}^2~.
  • Cụ thể hơn, nếu tổng ~c_{1}^2 + \dots + c_{Q}^2~ của bạn là ~S_p~, tổng ~c_{1}^2 + \dots + c_{Q}^2~ của BTC là ~S_j~, ~P~ là số điểm của test, thì điểm của bạn nhận được trong test đó là: ~\min \left(\frac{S_p}{S_j} * P * 95\%, P \right)~. Test ví dụ có điểm là ~0~.

Sample Input

3 4 2
1 1 2 3
1 2 2 3
2 2 3 3

Sample Output

3 3 2
1 1 2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.