| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem E
货币兑换
Time Limit: 1000ms
Memory Limit: 65536kb Description
招商银行遇到一位很奇怪的顾客。这位顾客起初用一些人民兑换了另一种货币，然后不断地用一种货币兑换另一种货币，最后又换回人民币。令人惊奇的是，最后换回的人民币居然比他最初带来的多了一些。例如这样一个兑换过程： 假设1单位人民币兑换6.89单位火星币，1单位火星币兑换0.18单位水星币，1单位水星币兑换0.81单位人民币。 我们用1.20单位人民兑换得8.27单位火星币，然后用这8.27单位火星币兑换得1.49单位水星币，最后用1.49单位水星币兑换到1.21单位人民币。 奇迹就这样发生了。聪明的你一定已经发现了，这都是四舍五入的功劳。 当然这种事情在现实中是不可能的，但我们还是来研究一下这个问题。 假设共有n种货币，编号从1到n。我们最初持有m单位的货币1。已知各种货币之间兑换比率，每次兑换后都四舍五入到小数点后两位。请问兑换k次且换回到货币1后，最多能让我们持有的货币增加多少单位？ Input
输入包含多组数据。每组数据第一行包含两个整数：n (1≤n≤100), k (0≤k≤100)，第二行为一个实数m (0<m≤100)，精确到小数点后两位。这三个数的含义如上所述。 然后是n行，每行n个数，第i行的第j个数aij表示可以用单位货币i兑换aij单位的货币j，注意，不一定能反向兑换。若aij=0，则表示不能直接用货币i兑换货币j。显然不能用货币i换货币i，这样没有意义。 输入以n=k=0结束。 Output
对每组数据输出我们持有的货币1最多能增值多少，精确到小数点后两位。如果不可能增值，则输出”0.00”
Sample Input
3 3 1.20 0.00 6.89 0.00 0.00 0.00 0.18 0.81 0.00 0.00 1 0 1.00 0.00 0 0 Sample Output
0.01 0.00 |