Arbitrage

【题目描述】 最近金融行业中电脑的使用已经引起了争议，因为使用程序交易（旨在利用非常小的价格波动）的方法已被许多华尔街公司取缔。 计算机编程的道德规范是一个有许多棘手问题的新兴领域。 套利 (Arbitrage) 是在一种货币和另一种货币间交易，利用几种货币间汇率的微小差异实现盈利的行为。比如，如果$1.00美元能兑换0.7英镑，£1英镑能兑换9.5法郎，而1法郎能兑换0.16美元，则一个套利商人可以从$ 1.00开始兑换并最终获得1 × 0.7 × 9.5 × 0.16 = 1.064 美元，从而获得百分之6.4的利益。 你将编写一个程序，判定一个汇率序列能否产生上述的盈利方法。 为了使套利行为成功，一个兑换序列必须在同一种货币处起始和终止，但可以考虑任意的开始货币。 【输入格式】 输入文件包含多组数据。 每组数据第一行为货币数n (2 <= n <= 20) ，然后给出n行的汇率表。 汇率表按照行优先顺序排列，但是缺少所有的对角线元素（假定一种货币兑换自身汇率为1.0）。因此，表的第一行表示货币1与其他n - 1种货币间的汇率（即1单位货币1可以购买的货币i (2 <= i <= n) 的数量）。 （译者注：这一段不是很清楚，建议看样例明确概念） 【输出格式】 输出盈利超过1%(0.01)的交易序列，如果有多个则输出长度最小的。由于IRS（美国国内税收局）会注意到过长的交易序列，所有交易序列的长度不得超过n（该汇率表的货币数）。 对于每组数据，首先输出交易序列的起始货币，然后依次输出不超过n个整数，整数i代表汇率表中第i行的货币。序列中的第一个整数代表该交易序列的起始货币，它应该与序列中的最后一个数相同。 如果不存在一个长度不超过n的盈利序列，则输出"no arbitrage sequence exists"（不加引号）。 感谢@zhec 提供的翻译

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=40 [PDF](https://uva.onlinejudge.org/external/1/p104.pdf) 



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

1 2 1
1 2 4 1
no arbitrage sequence exists