每當職棒球季進行到尾聲,球隊間互相為了獲得冠軍而廝殺之際,魔術數字便成為棒球迷的焦點。到底什麼是魔術數字呢?魔術數字什麼時候點亮?魔術數字要怎麼計算?請看以下的介紹。
一個聯盟中有許多球隊要爭取排名第一的位子。將球隊的勝場數除以已賽場次即可得到勝率,而球隊之間的戰績排行就以勝率為依據來做比較。假設戰績領先隊為 A 隊,其對 B 隊的魔術數字 $m_{AB}$ 存在的意義在於, B 隊已經無法自力阻止 A 隊封王。若 B 隊剩餘賽程全勝時(包括對 A 隊所有剩餘賽事皆獲得勝利),而 A 隊只需要對其他隊伍共贏得 $m_{AB}$ 場比賽, $m_{AB}$ 小於或等於( A 隊所剩的比賽場次 – A 隊與 B 隊剩餘對戰場次),使 A 隊在戰績排行上仍然領先 B 隊的話,則我們會說 A 隊對 B 隊的魔術數字已點亮,而點亮的魔術數字即是 $m_{AB}$ 。若 $m_{AB}$ 大於( 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 隊的魔術數字 $m_{AB}$ ,先假設落後隊 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 隊(與冠軍無緣)了。一般而言,只有領先隊伍與第二名隊伍間的魔術數字較為常用。但實際上,領先隊對所有其他隊伍都可能存在一個魔術數字。今天,你的任務是寫一個魔術數字計算程式。輸入每個球隊的隊名,戰績,和球隊間的剩餘對戰場次,你的程式除了能依球隊戰績排行輸出戰績表以外,還可以將求得的魔術數字輸出。
輸入檔可能包含多筆的測試資料。
每一筆測試資料的第一行有兩個數字 $n$ 和 $g$ 。第一個數字 $n (2 \le n \le 6)$ 表示聯盟的球隊數。第二個數字 $g (10 \le g \le 100)$ 則表示一個球隊在一個球季應出賽場次。第二行開始一共 $n$ 行,每一行依序包含了一隻球隊隊名,勝場數,和局數,敗場數。球隊的隊名由英文字母組成,最長為 9 個字母。勝場數,和局數,和敗場數皆為正整數,且其和不會超過 $g$。(你可以假設 $n$ 隻球隊中,必定只有一支球隊勝率最高。)
假設各球隊依在上述資料中出現順序分別編號為 $1,2, \cdots ,n$ 。在接下來的 $n$ 行中,每一行有 $n$ 個數字。第 $i$ 行的第 $j$ 個數字表示第 $i$ 支球隊與第 $j$ 支球隊的剩餘場數 $(1 \le i,j \le n)$ 。你可以假設測試資料都是合乎常理的數字,反映現實生活中計算魔術數字的情形。例如第 $i$ 行的第 $i$ 個數字一定為 0,因為自己球隊不可能跟自己球隊打。而第 $i$ 行的第 $j$ 個數字必定等於第 $j$ 行的第 $i$ 個數字。另外,一支球隊的對各隊的剩餘場數加上該球隊的已勝場數,和局數,以及已敗場數必定等於 $g$。
當測試資料第一行的輸入 $n$ 和 $g$ 皆為 0 時,表示測試資料全部結束,程式不需要對這行輸入作處理。
對於每一筆測試資料,請輸出一排版過的戰績表。依 $n$ 支球隊的戰績排名順序輸出 $n$ 行。除了第 1 名球隊以外,若發生勝率相同的情形,請依球隊在原資料的出現順序為輸出順序,但其排名則應並列。格式請參考範例輸出。隊名,勝率,魔術數字分別以一個空格來間隔,而隊名部分不足 9 個字元的部分則需填入空格。勝率固定輸出到小數點後三位(四捨五入)。第一名球隊不需要輸出魔術數字,請你分別計算出第一名球隊對其他球隊的魔術數字。若對其他球隊的魔術數字尚未點亮,請輸出 ”--”
。若魔術數字已點亮,則輸出 ”M”
以及該數字。測試資料之間請留一個空行。
※勝率=勝場數/(勝場數+敗場數)
儘管題目裡面已經有題示了,不過這裡還是要強調一下:p
原TIOJ1039 / NPSC2003初賽(prob B)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |