回分類題庫
d008: 2006 程式達人 G - 套利
出處:

Difficulity : 3
Accepted : 18 Times | Submit :101 Times | Clicks : 2097
Accepted : 13 Users | Submit : 16 Users | Accepted rate : 81%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2008-10-09 15:05

Content :

所謂的套利即是經由購買不同的貨幣,希望能藉著匯率上的差異而從中獲利。舉例來說:一元美金可以買到零點七元英鎊,一英鎊可以買到九點五法郎,而一法郎則可以買到零點一六元美金。一個採行這種交易方式的人可以靠著一元美金而賺到 1 x 0.7 x 9.5 x 0.16 = 1.064 元美金,獲利率是百分之六點四。

你要寫一個程式來找出那一種交易方式可以獲利。一次成功的套利交易必須以一種貨幣開始,並且以同一種貨幣為結束。但是任何貨幣都可以做為初始的貨幣種類。

Input :

輸入資料將包含一個或以上的貨幣匯率表。你必須為每一個表格求出一組解。每一個表格之前會有一個整數 n,表示了接下來這個表格的維度,最大的維度是20,而最小的維度則是2。

接下來的表格以一列列的順序輸入,但是不包含對角線上的元素(因為它們一定都是 1.0)。也就是說,輸入的第一列(表格的第一列)包含了第一種貨幣和其他 n-1 種貨幣的匯率。也就是說,一單位的第一種貨幣可以買到多少第 i (2 <= i <= n) 種貨幣。所以每個表格有n+1行的輸入資料,第一行只有n,接下來n行則包含了匯率表。

Output :

每個輸入的表格都必須要求出一組獲利率大於百分之一的交易序列。如果有符合要求的序列存在,就必須將之列出。當有一個以上符合要求的序列存在時,必須印出最短的序列,也就是交易最少次,但是仍然獲利的序列。

因為國稅局會監視連續交易,所以每個序列的長度必須保持在 n 以下,這裡的 n 表示的是匯率表的維度。如下的交易: 1 2 1 就包含了兩次的交易。

如果存在有可獲利的交易序列的話,你必須依照交易的順序印出。序列的表示法是一串的整數 i ,代表匯率表的 ith 行(第 i 個國家)。第一個整數是整個交易序列開始的國家,而這個數字也必須是整個交易的結束。

如果交易次數少於 n 的交易序列不存在,或是根本沒有可獲利的序列,那麼請輸出:

no arbitrage sequence exists

Sample Input :

3
1.2 .89
.88 5.1
1.1 0.15
4
3.1    0.0023    0.35
0.21   0.00353   8.13 
200    180.559   10.339
2.11   0.089     0.06111
2
2.0
0.45

Sample Output :

1 2 1
1 2 4 1
no arbitrage sequence exists

Hint :

題目原出處:ACMOJ 104

Author :

(管理員:MrWrongAnswer)

  Solve it!   Status Forum (1)

C++
C
JAVA
36658. nothinglo (4 ms , 498KB)
36656. MK (4 ms , 502KB)
36654. MK (4 ms , 732KB)
55377. johnny (6 ms , 364KB)
51259. uglyman (8 ms , 508KB)
55849. ag100 (4 ms , 324KB)
55378. johnny (6 ms , 370KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡