#P16573. [Euc2025]A Very Long Hike

[Euc2025]A Very Long Hike

题目描述

你计划在葡萄牙北部的佩内达-热雷什国家公园进行徒步旅行。公园的名字来自其中两座最高峰:佩内达峰(13401340 米)和热雷什峰(15451545 米)。

在本题中,公园被建模为一个无限整数平面。每个整数坐标位置 (x,y)(x,y) 都有一个确定的海拔高度。

海拔由一个 n×nn\times n 的矩阵 hh 周期性地铺满整个平面。具体地,对于任意整数 a,ba,b 以及 0≤x,y<n0\le x,y<n,位置

(x+an,y+bn)(x+an,y+bn)

的海拔为 h[x][y]h[x][y]。

当你位于 (x,y)(x,y) 时,可以移动到四个相邻位置之一:

(x,y+1),(x+1,y),(x,y−1),(x−1,y).(x,y+1),\quad(x+1,y),\quad(x,y-1),\quad(x-1,y).

若当前位置和目标位置的海拔分别为 alt⁡1\operatorname{alt}_1 和 alt⁡2\operatorname{alt}_2,则这次移动所需的时间为:

$$1+\left|\operatorname{alt}_1-\operatorname{alt}_2\right|.$$

你的初始位置为 (0,0)(0,0)。

请计算在 102010^{20} 秒内能够到达的不同整数位置数量。

当你的答案相对误差小于 10−610^{-6} 时,将被认为正确。也就是说,若你的输出为 xx,标准答案为 yy,则应满足:

∣x−y∣∣y∣<10−6.\frac{|x-y|}{|y|}<10^{-6}.

输入格式

第一行包含一个整数 nn:

2≤n≤20.2\le n\le 20.

接下来 nn 行,每行包含 nn 个整数。

第 i+1i+1 行的第 j+1j+1 个数为 h[i][j]h[i][j],其中:

0≤h[i][j]≤1545.0\le h[i][j]\le 1545.

输出格式

输出在 102010^{20} 秒内能够到达的不同整数位置数量。

答案相对误差小于 10−610^{-6} 即可。

样例 1

输入

2
3 3
3 3

输出

2e+40

说明

所有位置的海拔均为 33,因此任意一步移动都恰好耗时 11 秒。

位置 (x,y)(x,y) 在 102010^{20} 秒内可达,当且仅当:

∣x∣+∣y∣≤1020.|x|+|y|\le 10^{20}.

可达位置的精确数量为:

20000000000000000000200000000000000000001

它可以在相对误差要求内近似为 2×10402\times 10^{40}。

样例 2

输入

3
0 0 0
0 1545 0
0 0 0

输出

2e+40

说明

所有满足 x−1x-1 和 y−1y-1 都能被 33 整除的位置 (x,y)(x,y) 海拔为 15451545,其余位置海拔为 00。

例如,从 (4,10)(4,10) 移动到 (4,9)(4,9) 需要 15461546 秒,而从 (3,2)(3,2) 移动到 (4,2)(4,2) 只需 11 秒。

在 22 秒内可达的位置为所有满足 ∣x∣+∣y∣≤2|x|+|y|\le2 的位置,但不包含峰顶 (1,1)(1,1)。

在 102010^{20} 秒内可达位置的精确数量为:

19999999999999999931533333333333333863441

它同样可以在误差范围内近似为 2×10402\times10^{40}。

样例 3

输入

4
0 1 2 3
5 6 7 4
10 11 8 9
15 12 13 14

输出

1.524886878e+39