1333 . 蕃茄小豆湯
TopCoder
Tags
Description
你所管理的蕃茄小豆湯工廠最近出了點問題。因為年久失修，有一些用來裝填蕃茄小豆湯罐頭的機器故障了。
蕃茄小豆湯的生產線是這樣的: 首先，空的罐頭會先被放入紙箱中排好，然後讓整個紙箱進入生產線通過若干部機器，因為有些機器是故障的(可能是噴嘴塞住了)所以只能裝填部分的罐頭，所以需藉由數部機器的合作來完成裝填。然而已被裝填的罐頭就不能再被裝填，否則蕃茄小豆湯就會滿出來流得到處都是。
你的任務是找出最少需要多少部機器，才能完成可以裝滿每一個罐頭的生產線。
Input Format
輸入的第一行有兩個正整數N,M (N,M≤200)，表示有N台機器，M個罐頭要裝。
接下來有N行，每行有M個數為0或1，第i個數為0表示無法裝填第i個罐頭;為1表示可以裝填第i個罐頭。
Output Format
輸出最少需要幾部機器。
Sample Input 1
5 6
0 1 1 0 1 1
1 1 0 1 0 0
0 0 1 0 0 1
1 1 0 1 0 1
0 0 0 0 1 0
0 1 1 0 1 1
1 1 0 1 0 0
0 0 1 0 0 1
1 1 0 1 0 1
0 0 0 0 1 0
Sample Output 1
3
Hints
選擇第2,3,5部機器
Problem Source
原TIOJ1333 / Problem Setter：seanwu
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 14 |
| 2 | 1 | 14 |
| 3 | 2 | 14 |
| 4 | 3 | 14 |
| 5 | 4 | 14 |
| 6 | 5 | 14 |
| 7 | 6 | 16 |