TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

86.4% (19/22)

Submission's AC Ratio

22.6% (35/155)

Tags

Description

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

一個聯盟中有許多球隊要爭取排名第一的位子。將球隊的勝場數除以已賽場次即可得到勝率,而球隊之間的戰績排行就以勝率為依據來做比較。假設戰績領先隊為 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 隊(與冠軍無緣)了。一般而言,只有領先隊伍與第二名隊伍間的魔術數字較為常用。但實際上,領先隊對所有其他隊伍都可能存在一個魔術數字。今天,你的任務是寫一個魔術數字計算程式。輸入每個球隊的隊名,戰績,和球隊間的剩餘對戰場次,你的程式除了能依球隊戰績排行輸出戰績表以外,還可以將求得的魔術數字輸出。

Input Format

輸入檔可能包含多筆的測試資料。
每一筆測試資料的第一行有兩個數字 $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 時,表示測試資料全部結束,程式不需要對這行輸入作處理。

Output Format

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

Sample Input 1

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

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

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1