回分類題庫
h144: G.蚯蚓的智慧
關鍵字: NPSC 2014 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 22 Times / 17 Users | Submit : 154 Times / 36 Users | Accepted rate : 47%
題目加入時間 : 2015-11-10 13:39

Content: 简体中文

很多年前,蚯蚓王國受到鴨子王國的入侵。由於鴨子是蚯蚓的天敵之一,按照歷史記述一隻鴨子可以滅掉一整團蚯蚓。雖然蚯蚓數量非常多,但付出慘烈的代價之後,只稍微阻擋了鴨子的入侵腳步。

在一次高層的閉門會議後,蚯蚓們做出他們歷史上最大的決定:舉國遷移。由蚯蚓國首開先例,隨之還有許多同樣受到鴨子迫害的昆蟲,也跟著做出一樣的決定。史稱「昆蟲大遷徙」。

遷移後的蚯蚓維持了數百年,但近年鴨子王國不斷擴張,已經逐漸壓上蚯蚓國的邊境。有了歷史的教訓和近年動物學的研究,蚯蚓們知道抵抗天敵是不智的。

一籌莫展之際,突然鴨子國派來使者,表示要進行連年征戰的鴨子們膩了,想要進行和談。雖然蚯蚓們一時傻眼,不知道鴨子們的葫蘆裡賣的是什麼藥,但是這是除了再次遷徙外的唯一辦法了。蚯蚓們在無可奈何之下派出了蚯蚓國最聰明的兩隻蚯蚓,蚯蚯和蚓蚓,前往鴨子國處理和談事宜。

到了鴨子國,蚯蚯和蚓蚓發現鴨子們喜歡一個考驗運氣和默契的試煉,鴨子國的國王亦然。

「我們來進行這個神聖的試煉。如果你們的默契和運氣受到我們的認可,我們就放過你們。」鴨子國王如是說。

這個試煉主要是要讓兩隻蚯蚓個別猜硬幣,並且根據其結果評分,由此可以看出他們的運氣和默契綜合表現。在試煉開始前,鴨子國王告知了計分方式:

試煉總共有 n 個回合,每一回合會根據以下的流程進行:

  1. 參加試煉的兩隻蚯蚓可以討論這回合的戰術,討論完畢之後,兩隻蚯蚓必須被關掉兩個房間。然後接下來都不能有任何形式的溝通。
  2. 接著鴨子國王會在兩個相同的聖杯 A, B 裡,各擲入一枚正反面可以區別的金幣。金幣會在聖杯裡頭滾動,停下時會有一面朝上。由於鴨子國的工匠手藝相當精湛,這兩個硬幣落在聖杯裡出現正反面的機率是一樣的。
  3. 鴨子國王會把一個聖杯拿給蚯蚯看,並把另一個聖杯拿給蚓蚓看。所以兩隻蚯蚓會各別知道其中一個聖杯的金幣的狀態。
  4. 接下來就是考驗默契的時刻了,兩隻蚯蚓加起來就知道兩個硬幣的狀態,但他們必須在不可交流的情況下,個別猜另一個聖杯裡的金幣是正面還是反面。請注意兩隻蚯蚓在做決策的當下,並不知道另一個蚯蚓的作答情形。
  5. 鴨子國王在得到兩隻蚯蚓的答案之後,便會告訴他們這回合的試煉結果。當然他們可以從中計算這回合的得分。

最後 n 個回合的總分,就是蚯蚯和蚓蚓的得分。

明天就要進行這個重大的測驗了。事關蚯蚓國的存亡,你想要預測如果蚯蚯和蚓蚓每回合都能採取最佳策略的情況下,總分的期望值會是多少?

Input:

輸入的第一行有一個正整數 T 代表測試資料的筆數。

每一筆測試資料僅有一行,內有 4 個整數 n, a, b, c,分別表示測驗會持續 n 回合,且兩隻蚯蚓都猜中將獲得 a 分,僅其中一隻蚯蚓猜中則獲得 b 分,如果都沒猜中則獲得 c 分。

Output:

對於每一筆測試資料,請輸出在蚯蚯和蚓蚓在最佳策略的情況下,經過 n 回合之後,期望獲得的分數有多少。由於答案是個有理數,請輸出最簡分數,也就是輸出 p/q 使 gcd(p, q) = 1,且 q ≥ 1。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4
1 0 0 0
1 -1 -2 -3
1 1 2 3
5 5 5 5

Sample Output :

0/1
-2/1
2/1
25/1

Hint :

Author :

NPSC 2014 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum