G. Unevenness · AC 题库

Unevenness

AtCoder

⌀ 3731

翻译中…

Problem Statement

翻译中…

There is a grid with $N$ rows and $N$ columns. Let $(i,j)$ denote the cell at the $i$ -th row and $j$ -th column. $(i,j)$ contains an integer $A_{i,j}$ . You are also given two coprime positive integers $P$ and $Q$ .

翻译中…

You may perform the following operation any number of times (possibly zero), as long as the total cost does not exceed $\displaystyle \frac{P}{Q}$ :

翻译中…

Choose a positive real number $x$ . Choose one cell in the grid and either increase or decrease the value in that cell by $x$ . This operation incurs a cost of $x$ .

翻译中…

After performing all operations, let $B_{i,j}$ be the value in cell $(i,j)$ . Define the non-uniformity $U$ as the sum of absolute differences of adjacent cells. Formally,

翻译中…

$\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$ .

翻译中…

Find the minimum possible value of $U$ after performing the operations in an optimal way, and print that value. Also, print one valid final configuration $B_{i,j}$ that achieves this minimum $U$ .

翻译中…

Constraints

翻译中…

$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$
All input values are integers.

翻译中…

Input

翻译中…

The input is given from Standard Input in the following format:

翻译中…

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}

翻译中…

Output

翻译中…

Print $U$ and $B_{i,j}$ in the following format:

翻译中…

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}

翻译中…

Your output is considered correct if it meets all of the following conditions. (Note that the tolerance for $U$ is very strict.)

翻译中…

The absolute or relative error between your output $U$ and its true minimum value is at most $2^{-51} (\approx 4.44 \times 10^{-16})$ .
The absolute or relative error between $\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$ and $U$ is at most $10^{-10}$ .
$\sum_{i=1}^N \sum_{j=1}^N \vert A_{i,j} - B_{i,j}\vert$ is at most $\displaystyle \frac{P}{Q} + \max \left(1, \frac{P}{Q} \right) \times 10^{-10}$ .

翻译中…

If there are multiple solutions, you may print any one of them.

翻译中…

样例

Input #1

Output #1

24.0000000000000000000
3.0000000000000000000 4.0000000000000000000 1.0000000000000000000
3.0000000000000000000 4.0000000000000000000 2.0000000000000000000
5.0000000000000000000 7.0000000000000000000 9.0000000000000000000

By performing the following operations, we obtain $U = 24$, which is the minimum possible value. The total cost is $2 + 1 = 3$. - Let $x = 2$. Decrease the value in cell $(1,2)$ by $2$. - Let $x = 1$. Increase the value in cell $(2,1)$ by $1$.

Input #2

Output #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

Input #3

2 393 1
0 0
0 0

Output #3

0.0000000000000000000
0.0000000000000000000 0.0000000000000000000
0.0000000000000000000 0.0000000000000000000

Input #4

Output #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

Input #5

Output #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

Input #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

Output #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

题目信息

题号

abc393_g

所属比赛

AtCoder Beginner Contest 393

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。