2011年8月31日 星期三

436 - Arbitrage (II)


三角套利是利用匯率上的差異,將一塊錢換到超過一塊錢價值的同樣貨幣。例如1美元可以換0.5英磅,1英磅可以換10法郎,而1法郎可以換 0.21美元,藉由幾次交易,一個聰明的交易員可將一美元換成 0.5 * 10 * 0.21 = 1.05 美元,有5%的獲利。本題給定各貨幣間的匯率,請你判斷三角套利是否可行。

Input Specification

輸入會有一到多組測試資料,每組測試資料的第一列有一個整數 n (1 <= n <= 30)表示有 n 種不同貨幣,接下來的 n 列表示每種貨幣的名稱,名稱內不會有空白字元,接下來的一列有一個整數 m,表示接下來有 m 列貨幣匯率資料,每筆資料的格式為 A R B,表示A貨幣換到B貨幣的匯率為R,不存在於這 m 列匯率資料的貨幣兌換並不存在。每組測試資料間以一列空行隔開,當 n = 0表測試資料結束。

Output Specification

請針對每組測試資料輸出是否有套利的空間,其格式為:"Case case: Yes", 或"Case case: No"。

Sample Input

3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0

Sample Output

Case 1: Yes
Case 2: No


原文出處

沒有留言:

張貼留言