VM 10 Bài 03 - Tô màu
Xem dạng PDF
Gửi bài giải
Điểm:
2,00 (OI)
Giới hạn thời gian:
0.38s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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ụ:
Ở 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
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
chỉ mình với bạn ơi
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.