← 返回题目列表

Codeforces · 605/E

E. 星际旅行

中文机器翻译题面 查看原题

科学家最近发现了虫洞——太空中的物体,可以在星系和恒星系统之间进行很长的距离旅行。

科学家们知道有 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 }$$。