MCITYHAL - Repair City Hall

Because of its age, the City Hall has suffered damage to one of its walls.

A matrix with M rows and N columns represents the encoded image of that wall, where 1 represents an intact wall and 0 represents a damaged wall (like in Figure-1).



To repair the wall, the workers will place some blocks vertically into the damaged area. They can use blocks with a fixed width of 1 and different heights of {1, 2 ... M}.

For a given image of the City Hall’s wall, your task is to determine how many blocks of different heights are needed to fill in the damaged area of the wall, and to use the least amount of blocks.


There is only one test case. The case starts with a line containing two integers M and N (1 <= M, N <= 200). Each of the following M lines contains a string with length of N, which consists of “1”s and/or “0”s. These M lines represent the wall.


You should output how many blocks of different heights are needed. Use separate lines of the following format:

k Ck

where k ∈ {1, 2 ... M} means the height of the block, and Ck means the amount of blocks of height k that are needed. You should not output the lines where Ck = 0. The order of lines is in the ascending order of k.


5 10

1 7
2 1
3 2
5 1

Được gửi lên bởi:psetter
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Peiking 2004

hide comments
2017-10-30 15:00:28
ông cmt dưới làm gì gkê vậy :)) 2 for AC r
2017-08-31 04:14:13
3 vòng lặp + map -> 1hit ac
2016-07-21 11:46:50
Do Hong Huan chém gió vớ vẩn

Last edit: 2016-07-21 11:47:34
2015-11-19 15:50:55 Do Hong Huan
Bài này phải DFS+BFS+BIT+IT+Kruskal+BIGNUM+..v.v.. mới AC
2015-03-25 13:57:29
Không cần DFS, duyệt theo từng cột... 1 phát AC :)))))
2014-10-09 16:00:59 CTKB LHP
Đề troll =_=
Nếu cắt bất kì thì chắc hay hơn =)) =))
2014-09-21 18:22:09 Prismatic
O(n*(m+1)) :))
2014-09-21 18:22:09 Prismatic
O(n*(m+1)) :))
2014-08-24 03:37:57 ■■‡[ND] Bee Sociu■■‡
Code chuan 20 dong =))))
2014-08-13 06:16:55 Duc M. Pham
Bài này cần quái gì DFS nhỉ? DFS "mấy lớp" lại càng không @@
© All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.