AT_rcl_contest_2021_b マッサージチェア2021

在 X 先生工作的办公室闲置区，排列着一个 $N \times N$ 的按摩椅矩阵。每个按摩椅的位置用 $(i, j)$ 表示，其中 $i$ 是行号，$j$ 是列号。 这些按摩椅具有不同的**性能**。位于 $(i, j)$ 处的按摩椅的**性能**用 $1$ 到 $30$ 之间的整数 $E_{i, j}$ 表示，数值越大表示性能越好。此外，按摩椅的**功率**可以自由设置为 $0$ 到 $N$ 之间的整数，记为 $P_{i, j}$。 - 将**功率**设置为 $0$ 的按摩椅不会被使用，没人会坐。 - 将**功率**设置为非零值的按摩椅必须有人坐。 - 若按摩椅的**功率**设为 $P_{i, j}$（非零），则位于该按摩椅曼哈顿距离不超过 $P_{i, j}$ 距离内的其他按摩椅不得有人坐，因为会受到**噪音**影响。 下图示例展示了对部分按摩椅设置非零**功率**的情况。方格内的数字表示该位置按摩椅的**功率**，粉色方格中的按摩椅需保持无人使用。  在 X 先生为每个按摩椅设置**功率**后，所有**功率**不为 $0$ 的按摩椅将会有人坐在上面。坐在位于 $(i, j)$ 处按摩椅上的人将会获得的满意度为 $E_{i, j} \times P_{i, j}$。请尽可能地使所有坐在按摩椅上的人满意度之和达到最大。 各测试用例得分以及这一题的总得分计算方式如下： - 对于每个测试用例，所有坐在按摩椅上的人的满意度总和即为得分。 - 总共有 $50$ 个测试用例，每个测试用例得分的总和即为问题的总得分。

输入通过标准输入给出，格式如下： ``` \(\begin{array}{lll} N & & \\ E_{ 0,0 } & \ldots & E_{ 0,N-1 } \\ \vdots & \ddots & \vdots \\ E_{ N-1,0 } & \ldots & E_{ N-1,N-1 } \end{array}\) ``` - $N$ 表示按摩椅的行数和列数，总数为 $N = 40$。 - $E_{i, j}$ 表示第 $(i, j)$ 个按摩椅的**性能**，满足 $1 \leq E_{i, j} \leq 30$。

请输出 $N$ 行，每行含有 $N$ 个整数，作为标准输出： ``` \(\begin{array}{lll} P_{ 0,0 } & \ldots & P_{ 0,N-1 } \\ \vdots & \ddots & \vdots \\ P_{ N-1,0 } & \ldots & P_{ N-1,N-1 } \end{array}\) ``` - $P_{i, j}$ 代表第 $(i, j)$ 个按摩椅的**功率**，必须小于等于 $N$。 - 受到**噪音**影响的按摩椅的**功率**必须设置为 $0$。 - 如果输出结果不符合上述要求，将判定为 WA。 ## 提示 ### 测试用例生成说明 所有测试用例由一个测试用例生成器生成，可以通过链接获得。生成器按照以下方法生成用例，具体实现请查看代码： - 使 $E_{i, j}$ 取值为 $x$ 的概率与 $1/x^2$ 成正比，因此 $E_{i, j}$ 的值越大，其出现频率越低。 ### 提供的文件 提供了测试用例生成器、测试工具、样例数据和可视化工具： [测试用例生成器、测试工具、样例输入数据和可视化工具 (zip)](https://img.atcoder.jp/rcl-contest-2021/005883cbd767ff24197df17a19959035.zip) ### 可视化工具说明 我们提供了一个工具可以可视化输入输出的数据和得分。 - 本工具在最新版本的桌面版 [Google Chrome](https://www.google.co.jp/chrome/) 和 [Mozilla Firefox](https://www.mozilla.org/firefox/new/) 上进行了测试，但不能保证在所有浏览器上兼容。 - 工具计算的得分并不代表比赛中的实际得分，解答需通过提交到 AtCoder 完成评分。此外，工具计算的得分并不保证与比赛最终得分一致。 - 因使用该工具造成的任何损失概不负责。 可视化工具和使用说明包含在提供的文件中，详情请查阅文件中的 README.html。 ### 样例说明 - 样例 1 由于演示用，不符合输入约束（$N = 40$），得分计算为 $2 \times 1 + 5 \times 1 + 16 \times 4 = 71$。注意，**功率**不能大于 $N$。 - 样例 2 与测试工具中附带的 `input_0.txt` 相同，在这里省略输出示例。 **本翻译由 AI 自动生成**

### テストケースの生成について 各ケースはテストケースジェネレータによって生成されています。 テストケースジェネレータはページ下部のリンクより提供しています。 テストケースジェネレータは以下の手順でケースを生成します。厳密には実装を見てください。説明・実装ともに、必ずしも目を通す必要はありません。 - $ E_{\ i,j\ } $ が $ x $ になる確率は、 $ 1/x^2 $ に比例するように生成されます。すなわち、$ E_{\ i,j\ } $ が大きな値になるほど、出現する頻度が低くなります。 ### 配布物について テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザを次のリンクから提供しています。 [テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザ (zip)](https://img.atcoder.jp/rcl-contest-2021/005883cbd767ff24197df17a19959035.zip) ### ビジュアライザの説明 入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。 - このビジュアライザはデスクトップ版の [Google Chrome](https://www.google.co.jp/chrome/) および [Mozilla Firefox](https://www.mozilla.org/firefox/new/) の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。 - このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。 - このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。 ビジュアライザは配布物にも含まれ、使用方法については配布物内のREADME.htmlに記述があります。 ### Sample Explanation 1 このケースは説明用のもので、入力の制約（ $ N\ =\ 40 $ ）を満たしていません。 $ 2\ \times\ 1\ +\ 5\ \times\ 1\ +\ 16\ \times\ 4\ =\ 71 $ がスコアとなります。\*\*パワー\*\*に $ N $ より大きな整数を設定できないことに注意してください。 ### Sample Explanation 2 このケースは、テスターに同梱している `input\_0.txt` と同じものです。\*\*性能\*\*が高いものほど、出現頻度が低くなります。 出力例は省略します。