Repair City Hall

View as PDF

Submit solution


Points: 0.14 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Peiking 2004
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.