| City Hall | Solution | Tests |
Because of its age, the City Hall has suffered damages at one of its walls. The encoded image of that wall is represented by a matrix with m rows and n columns, like in the figure below:
1110000111 where 1 represents intact wall
1100001111 0 damaged wall
1000000011
1111101111
1110000111
The budget for repairing the City Hall will be given to those that will help the workers repairing this building, by placing vertically, some blocks of heights k , kÎ {1,2, ..., m} and the width equal to 1, in the damaged areas.
Task
For a given structure of the City Hall’s wall, determine the minimum number of blocks of heights k , k={1,2, ..., m}, needed for repairing the building.
Input format
The input file CH.IN contains on the first line the dimensions of the wall m and n, and on each of the next m lines, n characters 1 or 0, representing the wall.
Output format
The file CH.OUT will contain on each row sequences ordered by k :
k nr - where k is the height of the block,
- and nr is the number of blocks of k height, separated by space.
Restrictions
Example:
| CH.IN |
|
5 10 1110000111 1100001111 1000000011 1111101111 1110000111
|
| CH.OUT |
|
1 7 2 1 3 2 5 1 |
Time limit: 1 second/test