G - Unevenness Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 675 点

問題文

縦 N マス、横 N マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と呼びます。(i, j) には整数 A_{i,j} が書かれています。
また、互いに素な正整数 P, Q が与えられます。
あなたは次の操作を 0 回以上自由に行うことが出来ます。ただし、操作により発生するコストの総和が \displaystyle \frac{P}{Q} を超えてはいけません。

  • 正の実数 x を選ぶ。マスを 1 つ選び、選んだマスに書かれている数を x 増やすか x 減らす。この操作にはコストが x かかる。

操作を全て終了した後の (i, j) に書かれている数を B_{i,j} とします。この時、 不揃いさ U を隣接する要素の差分の総和として定義します。厳密に述べると、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 が最小になるように操作を行った時の U の値を出力してください。 また、U が最小になるように操作を行った時の B_{i,j} の値としてあり得るものを 1 つ出力してください。

制約

  • 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 および B_{i,j} が以下の条件を満たす時に正答となる。(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) に書かれている数を 2 減らす。
  • x=1 とする。(2,1) に書かれている数を 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

Score : 675 points

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.

Sample Input 1

3 3 1
3 6 1
2 4 2
5 7 9

Sample 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.

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

Sample 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

Sample Input 3

2 393 1
0 0
0 0

Sample Output 3

0.0000000000000000000
0.0000000000000000000 0.0000000000000000000
0.0000000000000000000 0.0000000000000000000

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

Sample 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

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

Sample 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

Sample 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

Sample 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