回分類題庫
d015: 98年台中區第五題
關鍵字: 98年台中區複賽

測資點 : 2 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 69 Times / 66 Users | Submit : 138 Times / 74 Users | Accepted rate : 89%
題目加入時間 : 2011-09-11 18:11

Content: 简体中文

電腦擇友問題

某一高科技網路通訊產品公司為了提供一個未婚員工找到合適伴侶的機會,特別舉辦電腦擇友活動,活動內容是由每一位參與者針對每位異性參與者給予一個評分,分數最低0分最高100分,所有人打完分數之後,A先生與B小姐的「速配程度」就是兩個人給對方打的分數的平均值,主辦單位為了讓每個人最後都能與異性配對,因此故意設計讓N個小姐與N位先生參與活動。

假定每位小姐與每位先生的「速配程度」都已經置於二維矩陣M[0..N-1][0..N-1]中, 每一列的資料代表某一位先生對所有小姐的「速配程度」,每一行的資料代表某一位小姐對所有先生的「速配程度」。

請幫忙該公司寫一個程式以取得下資訊:

  1. 不考慮最後是否每位小姐剛好與一位先生配對的限制,請問讓所有先生都最滿意的「速配程度」總分為何?
  2. 不考慮最後是否每位先生剛好與一位小姐配對的限制,請問讓所有小姐都最滿意的「速配程度」總分為何?
  3. 如果主辦單位不希望讓任何人有遺珠之憾,要求每一個小姐只能與一位先生配對,而且每一個先生也只能與一位小姐配對,請問滿足以上狀況的最高「速配程度」總分為何?

Input:

輸入資料第1列有一個數字p代表有幾組測試資料,使用者必須依此數字大小輸出p組答案。

第2列有一個數字N (2<N≦10)代表第一組測試資料的矩陣大小。

第3~(N+2)列是第一組測試資料的「速配程度」矩陣M的內容, 每一列的內容是矩陣內同一列的值, 同一列中的數字以空白間格。

接下來的內容是其他組測試資料的內容,其格式與第一組測試資料的格式相同。

Output:

請依照輸出範例,輸出每組的組別以及三種速配程度的總分,兩組資料中間請空一行。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3
65 90 70
80 90 60
70 80 75
4
60 70 80 90
90 90 90 90
70 70 70 70
95 85 75 65

Sample Output :

第1組測試資料結果
(1) 讓所有先生都最滿意的「速配程度」總分為260分
(2) 讓所有小姐都最滿意的「速配程度」總分為245分
(3) 完滿結局最高「速配程度」總分為245分

第2組測試資料結果
(1) 讓所有先生都最滿意的「速配程度」總分為345分
(2) 讓所有小姐都最滿意的「速配程度」總分為365分
(3) 完滿結局最高「速配程度」總分為345分

Hint :

註:原本題目為 N≦50,但官方版未提供較難的輸入測資,且從第二組輸出測資研判 N 應該最大只到 10 左右,故修改題目為 N≦10。

Author :

98年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum