← 返回题目列表

AtCoder · abc393_g

G. 不均匀

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

分数: 675 点

问题陈述

有一个网格 N 行和 N 列。让 (i,j) 表示位于 i第行和 j- 第列。 (i,j) 包含一个整数 A_{i,j}.
还给你两个互质正整数 P 和 Q.

您可以执行以下操作任意次数(可能为零),只要总成本不超过 \displaystyle \frac{P}{Q}:

  • 选择一个正实数 x。选择网格中的一个单元格,然后将该单元格中的值增加或减少 x。此操作的成本为 x.

执行完所有操作后,令 B_{i,j} 是单元格中的值 (i,j)。定义 不均匀性 U 作为相邻单元格的绝对差之和。正式地,

\displaystyle U = \sum_{i=1}^N \sum_{j=1}^{N-1} \vert B_{i,j} - B_{i,j+1} \vert + \sum_{i=1}^{N-1} \sum_{j=1}^N \vert B_{i,j} - B_{i+1,j} \vert.

找到最小可能值 U 以最佳方式执行操作后,并打印该值。另外,打印一份有效的最终配置 B_{i,j} 达到这个最小值 U.

约束

  • 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
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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 非常严格。)

  • 输出之间的绝对或相对误差 U 其真实最小值至多为 2^{-51} (\approx 4.44 \times 10^{-16}).
  • 之间的绝对或相对误差 \sum_{i=1}^N \sum_{j=1}^{N-1} \vert B_{i,j} - B_{i,j+1} \vert + \sum_{i=1}^{N-1} \sum_{j=1}^N \vert B_{i,j} - B_{i+1,j} \vert 和 U 最多是 10^{-10}.
  • \sum_{i=1}^N \sum_{j=1}^N \vert A_{i,j} - B_{i,j}\vert 最多是 \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

通过执行以下操作,我们得到 U = 24,这是可能的最小值。总成本是 2 + 1 = 3.

  • 让 x = 2。减少单元格中的值 (1,2) by 2.
  • 让 x = 1。增加单元格中的值 (2,1) by 1.

示例输入 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