2013年7月6日 星期六

10813 - Traditional BINGO

Problem E: Traditional BINGO

傳統的賓果遊戲(BINGO)通常可以在大廳以個人身分去玩,玩家們同時都在大廳,付一點遊戲費用。接著開始遊戲。賓果之夜舉行很多賓果遊戲,一場接著一場一直辦下去。

單一場賓果遊戲的流程是這樣子的:每名玩家都有一張賓果卡,玩家可能拿到不同種配置的盤面,每張賓果卡都是 5(row)x5(column) 的大小,共有 25 格的數字。

從最左邊的列(column) 到最右邊的列分別被標上字母 'B', 'I', 'N', 'G', 'O'。除了中心被標上 "free" 的格子是例外。而其餘數字的分布如下:

  • 'B' 列的每個數字範圍介於 1 - 15.
  • 'I' 列的每個數字範圍介於 16 - 30.
  • 'N' 列的每個數字範圍介於 31 - 45.
  • 'G' 列的每個數字範圍介於 46 - 60.
  • 'O' 列的每個數字範圍介於 61 - 75.
然而,每個數字只會出現一次。
這裡有個簡單的賓果卡:


B I N G O
10 17 39 49 64
12 21 36 55 62
14 25 FREE
SPACE
52 70
7 19 32 56 68
5 24 34 54 71

獨一無二的賓果卡個數相當多,根據公式可以被計算個數:

// the B, I, G, and O columns * the N column
(15 * 14 * 13 * 12 * 11) ^ 4 * (15 * 14 * 13 * 12)

或許這對統計學家是件有趣的事,由於賓果卡的個數可能不會影響玩家的勝率。
因此這裡將會有 75 個可能的賓果數字

B1, B2, B3, ... B15, I16, I17, I18, ... I30, N31, N32, ... O74, O75.
 
每一個數字都被標記在球上,並且丟入大型旋轉桶中。廣播員將會旋轉滾筒,並且抽出一個球告知所有在場玩家。每個玩家將會查看手中的賓果卡,如果存在這個數字,並將那格標記。而玩家可以在任何時間將中間的 FREE SPACE 標記。

當其中一個玩家有一個賓果連線(5 個標記出現在同行、同列或對角線)時,他便可喊出賓果,此時遊戲將會中斷。如果這名玩家確定是獲勝者,遊戲將會結束,並且開新的一場。否則,遊戲將會繼續報出賓果數字,直到出現一名獲勝者。

第一行,將會有一個整數 n 代表接下來有幾場賓果遊戲,而每場賓果遊戲的描述如上述。
假設手上只有一張賓果卡且沒有其他玩家,你必須決定手上的賓果卡何時獲得勝利,

接著,會有五行(row),每行將會有五個整數。其中第三行將只會有 4 個整數,因為 FREE SPACE 的存在。接下來會有 75 個數字,而這些整數範圍介於 1 - 75。

對於每組賓果遊戲,輸出 "BINGO after n numbers announced"
 

Chances of Winning

每次賓果遊戲將會有一張勝利的卡,所以玩家將獲勝的機會將取決於手上的卡,以及這場遊戲買了多少張卡 。例如一名玩家有 12 張卡,而整場遊戲中有 1200 張卡。他的勝率將會有 1%。

Sample Input

1
10 17 39 49 64
12 21 36 55 62
14 25 52 70
7 19 32 56 68
5 24 34 54 71
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75

Output for Sample Output

BINGO after 14 numbers announced

adapted from http://www.iam.ubc.ca/guides/javatut99/together/bingo/traditional.html