AT_abc393_g.[ABC393G] Unevenness
NOI/NOI+/CTSC
通过率：0%
AC君温馨提醒
该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。
题目描述
给定一个 $ N \times N $ 的网格。从上往下第 $ i $ 行、从左往右第 $ j $ 列的格子记为 $ (i,j) $，其中写有整数 $ A_{i,j} $。
同时给定两个互质的正整数 $ P $ 和 $ Q $。
你可以进行任意次数（包括零次）以下操作，但所有操作产生的总成本不得超过 $ \displaystyle \frac{P}{Q} $：
- 选择一个正实数 $ x $，并选择一个格子，将该格子中的数值增加或减少 $ x $。此操作的成本为 $ x $。
所有操作结束后，设 $ (i,j) $ 中的数值为 $ B_{i,j} $。此时定义不均衡度 $ U $ 为相邻元素差值的绝对值之和。严格来说，$ U $ 由以下公式定义：
$ \displaystyle U = \sum_{i=1}^N \sum_{j=1}^{N-1} |B_{i,j} - B_{i,j+1}| + \sum_{i=1}^{N-1} \sum_{j=1}^N |B_{i,j} - B_{i+1,j}| $
请输出通过操作使 $ U $ 最小化时的 $ U $ 值，并输出此时 $ B_{i,j} $ 的一个可能方案。
输入格式
输入通过标准输入给出，格式如下：
$ N $ $ P $ $ Q $
$ A_{1,1} $ $ A_{1,2} $ $ \dots $ $ A_{1,N} $
$ A_{2,1} $ $ A_{2,2} $ $ \dots $ $ A_{2,N} $
$ \vdots $
$ A_{N,1} $ $ A_{N,2} $ $ \dots $ $ A_{N,N} $
输出格式
按以下格式输出 $ U $ 和 $ B_{i,j} $：
$ U $
$ B_{1,1} $ $ B_{1,2} $ $ \dots $ $ B_{1,N} $
$ B_{2,1} $ $ B_{2,2} $ $ \dots $ $ B_{2,N} $
$ \vdots $
$ B_{N,1} $ $ B_{N,2} $ $ \dots $ $ B_{N,N} $
输出的 $ U $ 和 $ B_{i,j} $ 需满足以下条件才能视为正确（注意 $ U $ 的精度要求严格）：
- $ U $ 的真值与输出值的绝对误差或相对误差不超过 $ 2^{-51} \ (\approx 4.44 \times 10^{-16}) $；
- $ \sum_{i=1}^N \sum_{j=1}^{N-1} |B_{i,j} - B_{i,j+1}| + \sum_{i=1}^{N-1} \sum_{j=1}^N |B_{i,j} - B_{i+1,j}| $ 与 $ U $ 的绝对误差或相对误差不超过 $ 10^{-10} $；
- $ \sum_{i=1}^N \sum_{j=1}^N |A_{i,j} - B_{i,j}| $ 不超过 $ \displaystyle \frac{P}{Q} + \max\left(1, \frac{P}{Q}\right) \times 10^{-10} $。
若存在多个合法答案，输出任意一个均可。
输入输出样例
输入#1
3 3 1 3 6 1 2 4 2 5 7 9
输出#1
24.0000000000000000000 3.0000000000000000000 4.0000000000000000000 1.0000000000000000000 3.0000000000000000000 4.0000000000000000000 2.0000000000000000000 5.0000000000000000000 7.0000000000000000000 9.0000000000000000000
输入#2
5 3 1 1 1 1 1 1 1 3 3 3 1 1 3 2 3 1 1 3 3 3 1 1 1 1 1 1
输出#2
20.5714285714285714281 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 2.7142857142857142857 2.7142857142857142857 2.7142857142857142857 1.0000000000000000000 1.0000000000000000000 2.7142857142857142857 2.7142857142857142857 2.7142857142857142857 1.0000000000000000000 1.0000000000000000000 2.7142857142857142857 2.7142857142857142857 2.7142857142857142857 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000
输入#3
2 393 1 0 0 0 0
输出#3
0.0000000000000000000 0.0000000000000000000 0.0000000000000000000 0.0000000000000000000 0.0000000000000000000
输入#4
5 36 5 4 8 7 5 4 0 6 8 3 5 3 7 1 4 5 4 7 1 5 6 2 0 2 4 6
输出#4
71.4000000000000000014 4.0000000000000000000 8.0000000000000000000 7.0000000000000000000 5.0000000000000000000 4.0000000000000000000 2.2285714285714285714 6.0000000000000000000 7.0000000000000000000 4.0000000000000000000 5.0000000000000000000 3.0000000000000000000 7.0000000000000000000 1.7428571428571428571 4.0000000000000000000 5.0000000000000000000 4.0000000000000000000 7.0000000000000000000 1.7428571428571428571 5.0000000000000000000 6.0000000000000000000 2.0000000000000000000 1.4857142857142857144 2.0000000000000000000 4.0000000000000000000 6.0000000000000000000
输入#5
5 160 7 6 3 2 7 9 0 1 5 5 7 7 8 4 7 5 4 0 8 5 6 3 6 1 9 0
输出#5
65.4285714285714285685 6.0000000000000000000 3.0000000000000000000 3.0000000000000000000 7.0000000000000000000 9.0000000000000000000 1.0000000000000000000 1.0000000000000000000 5.0000000000000000000 5.0000000000000000000 7.0000000000000000000 7.0000000000000000000 7.0000000000000000000 5.0000000000000000000 5.0000000000000000000 5.0000000000000000000 4.0000000000000000000 4.0000000000000000000 5.0000000000000000000 5.0000000000000000000 5.0238095238095238086 3.0000000000000000000 5.0238095238095238086 5.0000000000000000000 5.0952380952380952371 0.0000000000000000000
输入#6
10 193926872645 2752096782 5 0 8 0 0 2 6 5 4 5 5 5 5 9 7 0 3 3 6 5 0 0 0 2 7 2 8 0 5 9 4 8 2 5 8 2 4 9 2 0 8 7 3 2 8 4 7 9 8 4 4 1 0 4 9 3 7 5 8 7 1 6 2 6 5 3 5 4 7 9 7 3 7 6 3 9 3 2 2 5 8 9 3 6 3 0 8 6 4 0 0 0 9 7 6 2 1 9 7 6
输出#6
346.6045935084415210714 5.0000000000000000000 5.0000000000000000000 5.0943878534377365339 0.0000000000000000000 0.0000000000000000000 2.0000000000000000000 5.0314626178125788449 5.0000000000000000000 5.0000000000000000000 5.0000000000000000000 5.0000000000000000000 5.0000000000000000000 5.0000000000000000000 7.0000000000000000000 7.0000000000000000000 2.0000000000000000000 3.0000000000000000000 3.0000000000000000000 5.0000000000000000000 5.0000000000000000000 0.0000000000000000000 0.0000000000000000000 0.0000000000000000000 2.0000000000000000000 7.0000000000000000000 2.0000000000000000000 4.0000000000000000000 3.0000000000000000000 5.0000000000000000000 5.1258504712503153793 4.0000000000000000000 7.0000000000000000000 2.0000000000000000000 5.0000000000000000000 8.0000000000000000000 2.0000000000000000000 4.0000000000000000000 8.0314626178125788445 2.0000000000000000000 2.0000000000000000000 7.0314626178125788445 7.0000000000000000000 3.0000000000000000000 3.0000000000000000000 8.0000000000000000000 4.0000000000000000000 7.0000000000000000000 8.0314626178125788445 8.0000000000000000000 4.0000000000000000000 4.0000000000000000000 2.0000000000000000000 2.0000000000000000000 4.0000000000000000000 8.0000000000000000000 3.0000000000000000000 7.0000000000000000000 5.0000000000000000000 8.0000000000000000000 7.0000000000000000000 4.0000000000000000000 6.0000000000000000000 2.0000000000000000000 6.0000000000000000000 5.0000000000000000000 3.0000000000000000000 5.0000000000000000000 4.0000000000000000000 7.0000000000000000000 7.0629252356251576894 7.0000000000000000000 6.0000000000000000000 6.0000000000000000000 6.0000000000000000000 3.0000000000000000000 3.0000000000000000000 3.0000000000000000000 3.0000000000000000000 3.0000000000000000000 5.0000000000000000000 8.0000000000000000000 8.0000000000000000000 6.0000000000000000000 6.0000000000000000000 3.0000000000000000000 2.0000000000000000000 6.0000000000000000000 6.0000000000000000000 4.0000000000000000000 4.0000000000000000000 0.0000000000000000000 0.0000000000000000000 7.0629252356251576894 7.0000000000000000000 6.0000000000000000000 2.0000000000000000000 2.0000000000000000000 7.0629252356251576894 7.0000000000000000000 6.0000000000000000000
说明/提示
约束条件
- $ 2 \leq N \leq 10 $
- $ 1 \leq P \leq 10^{12} $
- $ 1 \leq Q \leq 10^{12} $
- $ \gcd(P, Q) = 1 $
- $ 0 \leq A_{i,j} \leq 10 $
- 输入中所有值均为整数
样例解释 1
通过以下操作可使 $ U = 24 $，这是不均衡度的最小值。此时总成本为 $ 2 + 1 = 3 $：
- 选择 $ x=2 $，将 $ (1,2) $ 中的数值减少 $ 2 $；
- 选择 $ x=1 $，将 $ (2,1) $ 中的数值增加 $ 1 $。
翻译由 DeepSeek R1 完成
输入解题思路，AI测评打分。不知道怎么写?