TopCoder

Thumb 3ac79f3df8dcd1001410d90a738b4710b9122f08
矢澤にこ
にっこにっこにー♪ あなたのハートににこにこにー♪ 笑顔届ける矢澤にこにこー♪ にこにーって覚えてラブにこー♪

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

29.6% (8/27)

Description

每當職棒球季進行到尾聲,球隊間互相為了獲得冠軍而廝殺之際,魔術數字便成為棒球迷的焦點。到底什麼是魔術數字呢?魔術數字什麼時候點亮?魔術數字要怎麼計算?請看以下的介紹。

一個聯盟中有許多球隊要爭取排名第一的位子。將球隊的勝場數除以已賽場次即可得到勝率,而球隊之間的戰績排行就以勝率為依據來做比較。假設戰績領先隊為A隊,其對B隊的魔術數字mAB存在的意義在於,B隊已經無法自力阻止A隊封王。若B隊剩餘賽程全勝時(包括對A隊所有剩餘賽事皆獲得勝利),而A隊只需要對其他隊伍共贏得mAB場比賽,mAB小於或等於(A隊所剩的比賽場次 – A隊與B隊剩餘對戰場次),使A隊在戰績排行上仍然領先B隊的話,則我們會說A隊對B隊的魔術數字已點亮,而點亮的魔術數字即是mAB。若mAB大於(A隊所剩的比賽場次 – A隊與B隊剩餘對戰場次)時,此時A隊對B隊的魔術數字尚未出現。換句話說,B隊只要一鼓作氣連勝到底,戰績就可以超越或追平A隊,不需要巴望著A隊敗給其他球隊。

舉例來說明魔術數字的計算方法:A隊應賽50場,已賽35場,戰績26勝9敗,勝率0.743。B隊應賽50場,已賽34場,戰績20勝13敗1和,勝率0.606。而A隊與B隊剩餘賽程為3場。要計算A隊對B隊的魔術數字mAB,先假設落後隊B隊剩餘賽程全勝,也就是B隊贏得剩餘16場比賽,戰績36勝13敗1和,勝率0.735。而A隊輸掉3場與B隊的對戰,戰績26勝12敗,剩餘賽事15-3=12場。以討論的方式來檢查A隊至少要再贏m場,勝率就必定超過B隊。

m A隊勝率
8 0.68 < 0.735
9 0.7 < 0.735
10 0.72 < 0.735
11 0.74 > 0.735

由於討論所得到的m為11,小於12 (A隊剩餘場次 – A隊與B剩餘對戰場次=15-3=12),因此A隊對B隊魔術數字已點亮,且魔術數字為11。當A隊對B隊的魔術數字歸零時,表示B隊的戰績已經篤定無法超越A隊(與冠軍無緣)了。一般而言,只有領先隊伍與第二名隊伍間的魔術數字較為常用。但實際上,領先隊對所有其他隊伍都可能存在一個魔術數字。今天,你的任務是寫一個魔術數字計算程式。輸入每個球隊的隊名,戰績,和球隊間的剩餘對戰場次,你的程式除了能依球隊戰績排行輸出戰績表以外,還可以將求得的魔術數字輸出。

Input Format

輸入檔可能包含多筆的測試資料。
每一筆測試資料的第一行有兩個數字n和g。第一個數字n (2≤n≤6)表示聯盟的球隊數。第二個數字g (10≤g≤100)則表示一個球隊在一個球季應出賽場次。第二行開始一共n行,每一行依序包含了一隻球隊隊名,勝場數,和局數,敗場數。球隊的隊名由英文字母組成,最長為9個字母。勝場數,和局數,和敗場數皆為正整數,且其和不會超過g。(你可以假設n隻球隊中,必定只有一支球隊勝率最高。)
假設各球隊依在上述資料中出現順序分別編號為1,2,…,n。在接下來的n行中,每一行有n個數字。第i行的第j個數字表示第i支球隊與第j支球隊的剩餘場數(1≤ i,j ≤n)。你可以假設測試資料都是合乎常理的數字,反映現實生活中計算魔術數字的情形。例如第i行的第i個數字一定為0,因為自己球隊不可能跟自己球隊打。而第i行的第j個數字必定等於第j行的第i個數字。另外,一支球隊的對各隊的剩餘場數加上該球隊的已勝場數,和局數,以及已敗場數必定等於g。
當測試資料第一行的輸入n和g皆為0時,表示測試資料全部結束,程式不需要對這行輸入作處理。

Output Format

對於每一筆測試資料,請輸出一排版過的戰績表。依n支球隊的戰績排名順序輸出n行。除了第1名球隊以外,若發生勝率相同的情形,請依球隊在原資料的出現順序為輸出順序,但其排名則應並列。格式請參考範例輸出。隊名,勝率,魔術數字分別以一個空格來間隔,而隊名部分不足9個字元的部分則需填入空格。勝率固定輸出到小數點後三位(四捨五入)。第一名球隊不需要輸出魔術數字,請你分別計算出第一名球隊對其他球隊的魔術數字。若對其他球隊的魔術數字尚未點亮,請輸出”--”。若魔術數字已點亮,則輸出”M”以及該數字。測試資料之間請留一個空行。

Sample Input

4 6
Cubs 4 0 0
RedSoxs 2 0 2
Dodgers 2 0 2
Yankees 0 0 4
0 0 0 2
0 0 2 0
0 2 0 0
2 0 0 0
6 50
Banana 25 3 8
Guava 22 4 10
Cow 18 3 12
Fish 18 1 14
Moon 6 3 25
Monkey 6 4 26
0 4 3 4 3 0
4 0 0 3 4 3
3 0 0 6 4 4
4 3 6 0 1 3
3 4 4 1 0 4
0 3 4 3 4 0
0 0

Sample Output

1:Cubs      1.000
2:RedSoxs   0.500 M1
2:Dodgers   0.500 M1
4:Yankees   0.000 M0

1:Banana    0.758
2:Guava     0.688 --
3:Cow       0.600 M11
4:Fish      0.563 M9
5:Moon      0.194 M0
6:Monkey    0.188 M0

Hints

※勝率=勝場數/(勝場數+敗場數)

儘管題目裡面已經有題示了,不過這裡還是要強調一下:p

  • 2016/01/29 更新範例輸出。

Problem Source

原TIOJ1039 / NPSC2003初賽(prob B)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536