科学家最近发现了虫洞——太空中的物体,可以在星系和恒星系统之间进行很长的距离旅行。
科学家们知道有 n 个星系在他们的可达范围之内。您位于 1 号星系,需要前往 n 号星系。要从星系 i 到达星系 j,您需要飞到虫洞 (i, j),并且在恰好的一个星系日内,您将发现自己位于星系 j。
不幸的是,所需的虫洞并不总是可用。每个星系日它们都会随机消失和出现。然而,虫洞的状态不会在一个星系日内发生变化。从星系 i 到星系 j 的虫洞在每个星系日中都存在,以概率 pij 分开。你总是可以找出在给定时刻存在哪些虫洞。在每一时刻,你都可以通过此时存在的虫洞之一前往另一个星系,或者你可以简单地等待一个星系日,看看第二天会从你当前的位置通向哪些虫洞。
如果您以最佳方式行动,您的任务是找到从星系 1 旅行到星系 n 所需的预期时间值。保证这个期望值存在。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 1000) — 范围内的星系数量。
接下来是一个 n 行 n 列的矩阵。每个元素pij代表从星系i到星系j存在虫洞的概率。所有概率均以百分比形式给出,且均为整数。保证主对角线上的所有元素都等于100。
输出
打印一个实际值——如果一个人以最佳方式行动,从星系 1 到星系 n 所需时间的预期值。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
3 100 50 50 0 100 80 0 0 100
输出 #1
1.750000000000000
输入 #2
2 100 30 40 100
输出 #2
3.333333333333333
注意
在第二个样本中,从星系 1 到星系 2 的虫洞每天都会出现,概率等于 0.3。在该事件发生之前需要等待的天数的预期值为 $$\frac { 1 } { 0. 3 } = 3 \frac { 1 } { 3 }$$。