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 types
Allowed languages
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ụ:

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.


  • -2
    username001  commented on June 1, 2026, 4:03 p.m.

    Dành cho ai chưa biết, bài này ai sinh test thì người đó code được AC 100%


  • -2
    sp967845  commented on Nov. 21, 2025, 3:19 a.m. ← edited

    ok


  • 4
    luuthanhdatbienhoak66  commented on Sept. 7, 2025, 3:10 a.m.

    hello


  • 0
    cohanh12a4  commented on Aug. 26, 2025, 10:16 a.m. ← edited

    Hinh nhu chua co ai lam full het bai nay ma moi nguoi cao nhat dc 98.5/110


    • 1
      haiduong2110  commented on Feb. 19, 2026, 3:21 p.m.

      Hình như mấy bài VNOI Marathon là kiểu Heuristics (kiểu AHC), nên là gần như ko có ai có thể AC đc mấy bài này


  • -16
    vendettas  commented on Nov. 15, 2024, 5:52 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 1
      hieu0403  commented on April 12, 2025, 1:05 a.m.

      chỉ mình với bạn ơi


  • -9
    HDANTN  commented on Jan. 4, 2023, 6:56 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -238
    nam80022052  commented on Jan. 4, 2023, 4:03 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -53
      HDANTN  commented on Jan. 4, 2023, 6:57 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.