Repair City Hall

Xem dạng PDF

Gửi bài giải


Điểm: 0,14 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
Peiking 2004
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ma trận kích thước ~M~ hàng, ~N~ cột biểu diễn trạng thái các ô, ~1~-ô tốt, ~0~-ô hỏng.

1110000111
1100001111
1000000011
1111101111
1110000111

Ta sửa ma trận bằng 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, \dots, 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 \le~ ~M~, ~N \le~ ~200)~.
  • ~M~ dòng sau đó gồm ~N~ kí tự ~1~ hoặc ~0~.

Output

Gọi ~C_k~ là số khối có chiều cao ~k~ cần sử dụng. In ra một số dòng theo dạng ~k~ ~C_k~ theo thứ tự tăng dần của ~k~, với ~k \in \{1, 2, \dots, M\}~ và ~C_k \neq 0~.

Sample Input

5 10 
1110000111
1100001111
1000000011
1111101111
1110000111

Sample Output

1 7
2 1
3 2
5 1

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.