回分類題庫
h136: F.校園偶像計劃
關鍵字: NPSC 2014 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 27 Times / 22 Users | Submit : 81 Times / 30 Users | Accepted rate : 73%
題目加入時間 : 2015-11-10 13:33

Content: 简体中文

校園偶像 (school idols) 最近在各地都蔚為風潮,在穗香學園也不例外。一群對流行偶像文化感興趣的學生們組成了「偶像研究社」,並且創立了一個校園偶像團體。就和籃球社、棒球社等等社團附屬的社隊一樣,參與偶像研究社並創立校園偶像團體的學生們,不一定就是未來想要從事相關行業的人,只是因為有充分的熱誠和十足的興趣,想要在自己喜歡的領域展現自己青春的一面 ——校園偶像也就是因此而受到人們關注。

最近,為了響應這類校園偶像的活動,一個名為「我愛偶像」的比賽將在幾個月後舉辦。「我愛偶像」是一個校園偶像團體的全國大賽,只要是高中的校園偶像團體都可以參加。比賽首先會舉辦地區預賽,各區的前兩名隊伍則可以晉級最後的全國決賽。

熱衷於流行偶像文化的穗香學園偶像研究社成員們當然也要參與這場盛會。緊張又期待的心情可比棒球社的成員參加日本高中的夏季甲子園。由於種種原因,大家決定要從社員中選出九個人,並以九人一組的方式演出 (九個人登台似乎是現在的流行趨勢)。但也因為這項決定,使得要選擇哪些社員參賽便成了一個大問題。

根據分析,目前校園偶像們的吸引力大致上是由「笑容 (smile)」、「純真 (pure)」和「酷炫(cool)」三個面向組成的。如果越想要吸引觀眾和專業評審們的目光,就越得要加強這三大方面的表現。(當然,這些只是表現的技巧,實質的功力如歌唱舞蹈等等絕對也是必要的。) 另外,為了簡化問題,我們假設對於每一首歌曲,也都可以將它們分成「笑容」、「純真」和「酷炫」這三類。並且,我們簡單地定義一首歌的「整體表現」為「所有表演的成員對於該首歌類型的能力值之平均」。舉例而言,假設有一首歌屬於「笑容」類別,則該首歌的整體表現則以參加的九人的「笑容」能力值之平均值計算。隊伍的表演總分則是以每首歌的整體表現加總之。

在大家做完能力評估後,我們已經知道了穗香學園偶像研究社所有社員的三項能力值。表演的歌曲也已決定是以數首自行創作的歌曲參加,故所有屆時要演唱的歌曲的類型都已經知道了。於是給定大家的能力和歌曲類型,請你幫幫眾人找出最佳的九人組合。 

Input:

輸入的第一行有一個正整數 T,代表測試資料的筆數。

每一筆測試資料的第一行共有兩個正整數 N, M,代表穗香學園偶像社的成員人數。接下來有 N 行,每一行都有四個非負實數 ui, si, pi, ci 分別代表其中⼀個社員的學號及其三項能力值:「笑容」、「純真」和「酷炫」。所有的實數都精確到小數點下第三位。每筆測試資料的最後一行共有 M 的字元,表達參賽的歌曲類別。每一個 s 都對應到一首「笑容」類的歌曲;每一個 p 都對應到一首「純真」類的歌曲;每一個 c 都對應到一首「酷炫」類的歌曲。 

輸入檔所有於同一行的欄位內容都將以恰一個逗點「,」(不含引號) 分開。另外,輸入的成員資料將會按照學號從小到大的順序逐行呈現。

Output:

對於每一筆測試資料,請輸出兩行。

第一行請輸出最佳選擇可以得到的表演總分 (即可能的最高表演總分),請將數值四捨五入輸出至小數點下第三位。

第二行請輸出最佳選擇之九位成員的學號,並以恰一個逗點「,」(不含引號) 分開。成員的輸出順序請依照其學號從小到大輸出。

各筆測試資料所對應到的最佳解答都保證只有一組。

(注意:請不要在任何地方自行加上額外空白或其他字元。) 

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
10,3
1,2000.000,5000.000,3000.000
2,4000.000,2000.000,2000.000
3,1000.000,5000.000,3000.000
4,3000.000,2000.000,3000.000
5,2000.000,1000.000,5000.000
6,1000.000,3000.000,1000.000
7,1000.000,5000.000,3000.000
8,5000.000,3000.000,5000.000
9,4000.000,4000.000,4000.000
10,5000.000,1000.000,2000.000
s,p,c
12,5
1,796.501,13.025,994.582
2,676.916,409.636,561.610
3,848.811,443.469,586.526
4,221.629,653.935,608.985
5,589.992,555.418,413.737
6,539.929,334.949,46.011
7,547.726,103.542,559.104
8,934.054,673.369,373.407
9,860.740,995.345,3.964
10,553.694,620.526,438.781
11,48.880,503.052,638.534
12,213.942,398.149,963.539
s,p,s,c,c

Sample Output :

9444.444
1,2,3,4,5,7,8,9,10
2894.192
1,2,3,5,7,8,9,10,12

Hint :

Author :

NPSC 2014 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum