[HackerRank]ACM ICPC團隊(ACM ICPC Team)

題目描述

您將會得到要參加ACM-ICPC世界總決賽的N個參賽者的資料。每個參賽者都會精通或是不精通某些主題。若要將這N個參賽者分成兩人一隊,在這幾個隊伍中找出所有最多可以擅長幾項主題的隊伍,要能知道擅長主題和隊伍的數量。

假設a、b、c是不同的人,(a,b)和(b,c)是兩個不同的隊伍,也就是說同樣的人可以參加不同的隊伍。

原題網址

https://www.hackerrank.com/challenges/acm-icpc-team

輸入格式

第一行包含兩個整數,N和M,用空格隔開。N的範圍在2到500之間(包含2和500),為參賽者人數。M的範圍在1到500之間(包含1和500),為主題的數量。

接下來的N行,每行表示每個參賽者擅長與不擅長的科目,會用一個長度為M的二進制數量來表示。如果第i行,第j個字元為1,則表示第i個參散者,擅長第j個主題,若為0就表示不擅長。

輸出格式

在第一行輸出所有的隊伍組合中,能夠擅長的最大主題數量。

在第二行輸出有幾個能夠擅長的最大主題數量的隊伍。

範例輸入

4 5
10101
11100
11010
00101

範例輸出

5
2

額外解釋

隊伍(1,3)和(3,4)都擅長5種主題。

解題概念

利用三層巢狀迴圈,來計算出各種隊伍組合所能擅長的主題數量。接著只需將所有的主題數量儲存下來,接著再進行排序之後,即可非常容易取得擅長主題數量的最大值,然後也可輕易計算出相同的最大值數量有多少個。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章