C11BC3 - Color Ball
Giới hạn- Thời gian: 1.0s
- 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.
Trò chơi “Bi đổi mầu” là trò chơi đối kháng gồm hai người chơi trên lưới hình chữ nhật mxn ô vuông. Các dòng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm ở vị trí dòng i và cột j của lưới được gọi là ô (i,j) và khi đó, i được gọi là toạ độ dòng còn j được gọi là toạ độ cột của ô này.
Tại mỗi lượt chơi, mỗi người trong hai người chọn một hình vuông kích thước p × p của mình rồi bí mật viết ra một mảnh giấy hai số là tọa độ góc trái trên của hình vuông mà mình chọn. Sau đó cả hai công bố hình vuông của mình. Những viên bi nằm trong hình vuông mà hai người chơi chọn sẽ bị đổi màu, trừ những viên bi nằm trong cả hai hình vuông. Xét trường hợp bi của bạn là màu xanh .
+Gọi Sum(x,y,i,j) với 1<=i,x<=m-p+1 và 1<=j,y<=n-p+1 số bi xanh có được trên ma trận sau khi chọn hình vuông pxp có góc trên trái là (x,y) và đối phương chọn hình vuông pxp có góc trên trái là (i,j).
+Gọi Msum(x,y) là min(sum(x,y,i,j)) với mọi 1<=i<=m-p+1 và 1<=j<=n-p+1.
Yêu cầu: Tính tất cả Msum(x,y) với mọi 1<=x<=m-p+1 và 1<=y<=n-p+1.
Input
Dòng đầu tiên chứa số m,n,p (1<=m,n<=100, 1<=p<=min(m,n)).
m dòng sau: mỗi dòng chứ kí tự ‘0’ hoặc ‘1’ hoặc ‘2’ – ‘0’ tương ứng với ô không có bi, ‘1’ tương ứng với ô có bi xanh, ‘2’ tương ứng với ô có bi đỏ.
Output
Gồm m-p+1 dòng, mỗi dòng i chứa n-p+1 số nguyên là Msum(i,1), Msum(i,2), …, Msum(i,n-p+1).
Example
Input:6 8 5
00022112
20221022
01102101
01021122
02211112
21000001
Output:
12 13 12 16
14 15 14 16
33.33% số test với m,n <= 10.
33.33% số test tiếp theo với m,n<=50.
33.33% số test tiếp theo với m,n <= 100.
- Người up: songuku95
- Nguồn bài: lấy ý tưởng từ bảng C tin học trẻ toàn quốc nãm 2012. (khaihanhdk)