BPAINT - Tô màu
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274709/problem/C
https://codeforces.com/group/FLVn1Sc504/contest/272561/problem/M
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 x 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->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 + .... + c[Q]^2 càng lớn càng tốt.
Dữ liệu
- Dòng đầu tiên chứa 3 số n, m, k. (n, m, k <= 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.
Kết quả
- 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).
Ví dụ
Dữ liệu:
3 4 2
1 1 2 3
1 2 2 3
2 2 3 3
Kết quả:
3 3 2
1 1 2
Cách tính điểm
Điểm cho mỗi output hợp lệ sẽ tỷ lệ với tổng c[1]^2 + .... + c[Q]^2.
- Người up: voj
- Nguồn bài: VM10 - Tác giả: Khúc Anh Tuấn