d196: 11341 - Term Strategy
Tags :
Accepted rate : 54人/63人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-04-23 07:31

Content

學生彼得整學期都在玩撞球因而錯過了所有的課堂。不幸的是現在彼得必須通過他的期末考。

彼得修了N (1 <= N <= 10) 門課。時間已無多而且他答應老師要一天之內考完所有的試。他的哲學是「全拿或全輸」。在他做了一天只玩 5 小時撞球的假設及一些考量之後,他算出了他還有 M (0 < M <= 100) 個小時可以準備考試。在準備一個科目時,他至少得讀完該科目的名稱,由於這個困難的工作,每科至少要準備一個小時。如果有任何一科沒有準備,該科就會當掉。

考試的成績分為 10 級分。彼得要得到 5 級分才能及格。彼得也是個貪心的人,他希望平均成績越高越好。

由於彼得完全清楚自己的實力,他做了一個表格 L。表格中的每一列代表一科,每一欄代表彼得在該科所花的時間。Lij 代表彼得如果用 j 個小時去準備第 i 科時所能得到的成績。已知彼得在某科目所用的時間越多,所得的成績也會越高,也就是說. Li j >= Li j+1  

彼得突然想到他有一個好友。事實上,他所想到的人就是你。由於情況緊急,他請你幫忙找出可以 All Pass 並得到最高平均成績的方法。

Input

輸入的第一行會給你測試資料的組數T (T < 100)。每組測資的第一行有兩個整數N M。接下來的 N 行每行有 M 個整數代表 Li j

Output

對於每組測資,請找出彼得是否可以 All Pass。如果他可以 All Pass 請印出一行:「Maximal possible average mark - S. (答案 S 必須四拾五入到小數點以下兩位)

如果他不幸會當掉至少一科的話,則印出一行:「Peter, you shouldn't have played billiard that much.(彼得,你不該打那麼多撞球的。)

Sample Input
2
4 5
5 5 6 7 8
5 5 6 7 8
5 6 7 8 8
6 7 8 9 9
4 5
4 5 6 7 8
4 5 6 7 8
5 6 7 8 8
6 7 8 9 9
Sample Output
Maximal possible average mark - 5.50.
Peter, you shouldn't have played billiard that much.
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :

UVa 原題

若得到 WA (line:10) 請留意浮點數誤差。

Tags:
出處:
UVa11341 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」