← 返回题目列表

Codeforces · 2068/G

G. 一次很长的徒步旅行

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

您计划在葡萄牙北部的 Peneda-Gerês 国家公园徒步旅行。该公园因其两座最高峰而得名:Peneda(1340 m)和 Gerês(1545 m)。

对于这个问题,公园被建模为一个无限平面,其中每个位置 $$$(x, y)$$$(其中 $$$x, y$$$ 为整数)具有特定的高度。高度由 $$$n \times n$$$ 矩阵 $$$h$$$ 定义,该矩阵在平面上定期重复。具体来说,对于任何整数 $$$a、b$$$ 和 $$$0 \leq x, y \lt n$$$,$$$(x + an, y + bn)$$$ 处的海拔高度为 $$$h[x][y]$$$。

当您处于位置 $$$(x, y)$$$ 时,您可以移动到四个相邻位置中的任意一个:$$$(x, y+1)$$$、$$$(x+1, y)$$$、$$$(x, y-1)$$$ 或 $$$(x-1, y)$$$。在两个相邻位置之间移动所需的时间为 $$$1 + \lvert \text{alt}_1 - \text{alt}_2 \rvert$$$,其中 $$$\text{alt}_1$$$ 和 $$$\text{alt}_2$$$ 分别是当前位置和目的地位置的海拔高度。

最初,您的仓位为 $$$(0, 0)$$$。计算您在 $$$10^{20}$$$ 秒内可以到达的不同位置的数量。如果相对误差小于 $$$10^{-6}$$$,您的答案将被视为正确。

输入

第一行包含一个整数 $$$n$$$ ($$$2\le n\le 20$$$)——描述海拔高度的矩阵的大小。

以下 $$$n$$$ 行每行包含 $$$n$$$ 个整数。这些行中第 $$$(i+1)$$$ 上的第 $$$(j+1)$$$ 数字是 $$$h[i][j]$$$ ($$$0\le h[i][j] \le 1545$$$) — 位置 $$$(i, j)$$$ 的海拔高度。

输出

打印您在 $$$10^{20}$$$ 秒内可以到达的不同位置的数量。如果相对误差小于 $$$10^{-6}$$$,您的答案将被视为正确。

示例

输入
复制

2
3 3
3 3

输出
复制

2e+40

输入
复制

3
0 0 0
0 1545 0
0 0 0

输出
复制

2e+40

输入
复制

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

输出
复制

1.524886878e+39

注意

在 第一个样本,Peneda-Gerês 国家公园的每个位置的海拔均为 $$$3$$$。因此,在两个相邻位置之间移动所需的时间始终等于 $$$1$$$ 秒。

在这种情况下,可以证明位置 $$$(x, y)$$$ 在 $$$10^{20}$$$ 秒内可达,当且仅当 $$$|x|+|y| \le 10^{20}$$$。可以计算出存在 $$$20\,000\,000\,000\,000\,000\,000\,200\,000\,000\,000\,000\,000\,001$$$ 可到达位置,这个数字近似为 $$$2\cdot 10^{40}$$$,相对误差小于$$$10^{-6}$$$。示例输出显示 $$$2\cdot 10^{40}$$$ 作为正确答案,而且可到达位置的确切数量也是正确答案。

在 第二个样本,Peneda-Gerês 国家公园中 $$$x-1$$$ 和 $$$y-1$$$ 可被 $$$3$$$ 整除的每个位置 $$$(x, y)$$$ 的海拔均为 $$$1545$$$,而所有其他位置的海拔均为 $$$0$$$。例如,在 $$$(4, 10)$$$ 和 $$$(4, 9)$$$ 之间移动所需的时间为 $$$1546$$$,而在 $$$(3, 2)$$$ 和 $$$(4, 2)$$$ 之间移动所需的时间为 $$$1$$$。

$$$2$$$秒内可到达的位置是除了$$$(1, 1)$$$(处于峰值)之外的所有位置$$$(x, y)$$$且$$$|x|+|y|\le 2$$$。我们可以计算出在 $$$10^{20}$$$ 秒内存在 $$$19\,999\,999\,999\,999\,999\,931\,533\,333\,333\,333\,333\,863\,441$$$ 可到达位置,并且该数字近似为 $$$2\cdot 10^{40}$$$,相对误差小于$$$10^{-6}$$$。示例输出显示 $$$2\cdot 10^{40}$$$ 作为正确答案,而且可到达位置的确切数量也是正确答案。