MCITYHAL - Repair City Hall
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.
Ma trận kích thước M hàng, N cột biểu diễn tường, 1-tường tốt, 0-tường hỏng.
1110000111
1100001111
1000000011
1111101111
1110000111
Hình minh hoạ
Sửa = cách đặt các khối thẳng đứng vào các vùng hỏng. Các khối có thể sử dụng có độ rộng 1 và chiều cao có thể là {1,2, ..., M}. Cần xác định số khối từng loại sao cho số lượng khối là ít nhất.
Input
Dòng đầu là hai số M và N (1 <= M, N <= 200). M dòng sau đó gồm N kí tự 1 hoặc 0.Output
Xác định số khối cần sử dụng đối với từng chiều cao k Ck với k ∈ {1,2, ..., M} là chiều cao của khối và Ck là số khối cần sử dụng. Không in ra các dòng có Ck = 0 và in ra theo thứ tự tăng dần của k.Sample Input 5 10 1110000111 1100001111 1000000011 1111101111 1110000111
Sample output 1 7 2 1 3 2 5 1
- Người up: vdmedragon
- Nguồn bài: Peiking 2004