UVA104 Arbitrage

最近金融行业中电脑的使用已经引起了争议，因为使用程序交易（旨在利用非常小的价格波动）的方法已被许多华尔街公司取缔。计算机编程的道德规范是一个有许多棘手问题的新兴领域。 套利（Arbitrage）是在一种货币和另一种货币间交易，利用几种货币间汇率的微小差异实现盈利的行为。比如，如果 $1.00$ 美元能兑换 $0.7$ 英镑，$1$ 英镑能兑换 $9.5$ 法郎，而 $1$ 法郎能兑换 $0.16$ 美元，则一个套利商人可以从 $1.00$ 美元开始兑换并最终获得 $1 \times 0.7 \times 9.5 \times 0.16 = 1.064$ 美元，从而获得 $6.4\%$ 的利益。 编写一个程序，判定一个汇率序列能否产生上述的盈利方法。

输入文件包含多组数据。 每组数据第一行为货币数 $n$（$2 \leq n \leq 20$），然后给出 $n$ 行的汇率表。 汇率表按照行优先顺序排列，但是缺少所有的对角线元素（假定一种货币兑换自身汇率为 $1.0$）。因此，表的第一行表示货币 $1$ 与其他 $n - 1$ 种货币间的汇率，即 $1$ 单位货币 $1$ 可以购买的货币 $i$（$2 \leq i \leq n$）的数量。

输出盈利超过 $1\%$（$0.01$）的交易序列，如果有多个则输出长度最小的。由于 IRS（美国国内税收局）会注意到过长的交易序列，所有交易序列的长度不得超过 $n$（该汇率表的货币数）。 对于每组数据，首先输出交易序列的起始货币，然后依次输出不超过 $n$ 个整数，整数 $i$ 代表汇率表中第 $i$ 行的货币。序列中的第一个整数代表该交易序列的起始货币，它应该与序列中的最后一个数相同。 如果不存在一个长度不超过 $n$ 的盈利序列，则输出 `no arbitrage sequence exists`。

感谢 @zhec 提供的翻译、@nr0728 修正了 KaTeX