a259. 選裁判問題 - 彰化精誠中學

內容

pdf檔：請看pE

https://drive.google.com/file/d/1MjP-ZyqPJYtkp0utjxUdp2e3qhy92vGR/view?usp=sharing

身為 NPSC (National Program Squeezing Contest) 大賽的裁判長，最困難的其實不是把有趣且新奇的題目出出來，而是要從為數不多的裁判候選人中選出最適合的裁判群。目前共有 $N$ 位符合資格的裁判候選人，各各身懷絕技，能夠出各種讓參賽者會心一笑又不落俗套的有趣題目。但是，在這個小圈子中，裁判非常容易會認識參賽者，也許是學長姊跟學弟妹，也許是往日同隊的隊友，也可能是師徒關係。為了使 NPSC 成為一個公平、公正、公開的比賽，裁判長必須盡力的避嫌。因此，裁判長調查了這 $N$ 位符合資格的裁判候選人，以及 $M$ 位當屆 NPSC 報名的參賽者，將每位參賽者與裁判是否認識的關係蒐集起來。現在，裁判長決定組織一個恰好有 $K$ 位裁判的裁判團，裁判長想知道在所有可能的選擇當中，完全不與這 $K$ 位裁判相識的參賽者最多有幾位。也就是說，對於所有選定 $K$ 位裁判的方案中，與選定的 $K$ 位裁判皆不相識的參賽者總人數最多有幾人？由於裁判長仍在考慮最終題目的數量，因此他想知道對於所有可能的 $K$，最多能有多少滿足條件的參賽者。

輸入說明

輸入第一行，包含兩個以空格隔開的正整數 $N, M$，分別代表候選裁判人數，以及報名參加的參賽者總數。接下來 $N$ 行，每行包含一個長度為 $M$ 的 01 字串，若第 $i$ 行的第 $j$ 個字元為 '1'，則代表第 $i$ 位裁判與第 $j$ 位參賽者相識；若第 $i$ 行的第 $j$ 個字元為 '0'，則代表第 $i$ 位裁判與第 $j$ 位參賽者不相識。

• $1 ≤ N ≤ 20$

• $1 ≤ M ≤ 10^6$

輸出說明

請輸出 $N$ 行，第一行包含一個整數代表 $K = 1$ 時，最多能有多少位參賽者、第二行代表 $K = 2$ 時最多的參賽者數、...、第 $N$ 行代表 $K = N$ 時最多的參賽者數。

範例輸入 #1

2 3
110
010

範例輸出 #1

2
1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (3%): 1.0s , <10M
公開測資點#1 (3%): 1.0s , <10M
公開測資點#2 (3%): 1.0s , <1M
公開測資點#3 (3%): 1.0s , <1M
公開測資點#4 (3%): 1.0s , <10M
公開測資點#5 (3%): 1.0s , <10M
公開測資點#6 (3%): 1.0s , <10M
公開測資點#7 (3%): 1.0s , <10M
公開測資點#8 (3%): 1.0s , <50M
公開測資點#9 (3%): 1.0s , <50M
公開測資點#10 (3%): 1.0s , <1K
公開測資點#11 (3%): 1.0s , <1K
公開測資點#12 (3%): 1.0s , <1M
公開測資點#13 (3%): 1.0s , <1M
公開測資點#14 (3%): 1.0s , <1M
公開測資點#15 (3%): 1.0s , <1M
公開測資點#16 (3%): 1.0s , <1M
公開測資點#17 (3%): 1.0s , <1M
公開測資點#18 (3%): 1.0s , <10M
公開測資點#19 (3%): 1.0s , <10M
公開測資點#20 (3%): 1.0s , <50M
公開測資點#21 (3%): 1.0s , <50M
公開測資點#22 (3%): 1.0s , <50M
公開測資點#23 (3%): 1.0s , <50M
公開測資點#24 (4%): 1.0s , <50M
公開測資點#25 (4%): 1.0s , <1K
公開測資點#26 (4%): 1.0s , <1K
公開測資點#27 (4%): 1.0s , <1K
公開測資點#28 (4%): 1.0s , <1K
公開測資點#29 (4%): 1.0s , <1K
公開測資點#30 (4%): 1.0s , <1K

提示：

標籤:

出處:

[管理者：

haha (大學長)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」