#P4984. 旅行

    ID: 4084 传统题 1000ms 64MiB 尝试: 10 已通过: 5 难度: 8 上传者: 标签>难度分类提高+/省选-构造与建模图构造树算法LCA枚举与搜索深度优先搜索动态规划树形 DP组合数学贡献法CF2400

旅行

路标

题目描述

wby 国的城市在一座岛的海边,道路只修到足以连接所有城市,任意两座城市之间的路径唯一。沿任意城市间的路径,从起点开始每隔 11 千米有一个路标,城市和交叉路口也都设有路标。因此,每个路口到每座城市的距离都是整数千米。

给定所有城市两两之间的距离,求任意两个不同路标之间沿道路距离的平均值。如果给定的距离无法确定该值,则报告无法确定。

输入格式

第一行一个整数 nn,满足 2≤n≤5002\le n\le500。

随后 n−1n-1 行,第 ii 行包含 n−in-i 个整数,其中第 jj 个整数是城市 ii 与城市 i+ji+j 的距离。所有给定距离在 [1,106][1,10^6] 内。

输出格式

输出一行一个实数,表示不同路标两两之间的平均距离,允许绝对误差不超过 10−610^{-6}。无法确定时输出 impossible。

样例

3
4 4
2
2.13333333333333

原赛题面(NWERC 2016,D 题)