← 返回题目列表

AtCoder · rcl_contest_2021_b

B. 按摩椅2021

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

問題文

X先生工作的办公室里,N 行 N 按列排列了按摩椅。
从上到下第 i 行,从左 j 列的按摩椅坐标用 (i, j) 表示。

按摩椅有各种各样的性能。
(i, j) 中的按摩椅性能在 1 以上 30 以下的整数表示为 E_{i, j} ,数字越大表示越好。
另外, (i, j) 中的按摩椅的移动功率作为, 0 以上 N 以下的整数可以自由设定,设定在 P_{i, j} 。 除以

  • 功率是 0 的按摩椅将不会被使用,人也不会坐。
  • 功率是 0 之外的按摩椅套件总会有人坐在上面。
  • (i, j) 的按摩椅 0 之外 当使用功率 P_{ i, j } 运行时, 根据功率根据動作音可以被周围的人听到, (i, j) 起 曼哈顿距离 是 P_{i, j} 以下其他按摩椅必须保持无人使用。

下图显示了一些按摩椅 这是设置 0 之外 当使用功率的示例。方格内所写的整数就分配给该位置的按摩椅。功率表示任何人不得坐在位于粉色方块的按摩椅上。

X先生设置了每把按摩椅。功率后,功率是 0 人们坐在所有不是的按摩椅上。
(i, j) 按摩椅上的人 获得E_{ i,j } \times P_{ i,j } 满意。
请尽可能增加坐在按摩椅上的人获得的满足感总和。

每个测试用例和该问题的分数计算如下:

  • 在一个测试用例中,总分是坐在按摩椅上的人的总满意度。
  • 所有测试用例都是 有 50 。每个测试用例的总分就是该题的得分。

入力

输入通过标准输入以以下格式给出。
第一行是一个整数 包含一个 N 。继续 N 行包含由空格分隔的整数。 包含 N 块。

\(\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 ≤ E_{i,j} ≤ 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) 中的按摩椅的移动功率的整数,0 ≤ P_{i,j} ≤ N 。 按摩椅受
  • 動作音影响 请务必设置功率请将其设置为 0 。
  • 如果输出不满足上述约束, 。

关于测试用例生成

每个用例均由测试用例生成器生成。
测试用例生成器可从页面底部的链接获取。
测试用例生成器使用以下步骤生成用例。详情请参阅实现。没有必要把解释和实现都通读一遍。

  • E_{ i,j } 是 x 的概率是 生成与 1/x^2 成比例。也就是说,E_{ i,j } 的值越大,出现的频率越低。


入力例1

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
此案例仅供说明之用;输入约束( N = 40 )不满意。

出力例1

0 1 0 0
1 0 0 0
0 0 0 0
0 0 0 4
2 \times 1 + 5 \times 1 + 16 \times 4 = 71 是您的分数。 请注意,您不能设置大于功率至 如果添加 N 的整数。

入力例2

40
4 2 1 1 1 1 3 1 1 1 6 1 1 2 1 1 6 17 3 5 1 2 5 2 1 1 1 1 6 12 1 4 1 3 1 1 2 1 3 2
1 1 4 1 1 4 1 1 1 12 3 1 1 1 1 7 1 1 2 1 3 1 11 1 1 1 1 1 1 1 1 1 1 2 1 1 2 4 6 3
5 6 1 1 2 1 3 4 5 1 9 1 1 2 26 6 3 1 1 1 2 4 1 2 1 1 3 1 3 1 1 2 1 1 6 1 2 1 2 1
1 1 1 16 1 1 10 1 1 1 3 7 1 1 1 1 1 2 1 1 1 1 1 19 1 1 2 3 6 1 2 12 1 2 4 1 1 1 1 1
1 1 1 1 1 1 3 1 1 1 2 1 1 1 1 9 1 1 1 8 2 2 2 1 1 2 1 1 1 1 2 1 4 1 1 1 2 1 2 1
1 1 1 1 1 1 2 5 1 1 1 3 4 3 1 30 2 1 2 19 1 2 1 1 2 1 3 1 1 1 2 4 1 15 1 4 1 1 1 1
3 4 1 1 2 1 4 1 1 1 2 1 8 8 6 1 2 2 2 2 5 2 1 1 1 1 1 1 1 3 2 1 2 1 1 16 1 1 1 1
1 1 1 1 1 1 1 1 1 1 6 1 3 14 1 1 2 1 1 2 5 6 2 1 14 2 1 1 2 1 1 1 1 1 1 1 2 1 1 19
1 3 1 1 1 4 2 5 1 2 1 1 1 1 9 1 1 1 1 1 1 20 17 1 1 2 4 1 6 1 1 1 2 1 1 1 1 11 5 3
1 1 1 3 3 1 2 3 1 1 4 1 1 1 1 3 1 1 1 2 12 1 5 1 1 2 3 2 21 2 5 1 1 1 3 1 3 1 1 4
3 2 1 1 1 1 1 4 8 1 1 3 1 2 1 1 3 1 1 1 1 4 2 2 1 18 1 1 1 1 1 1 1 1 2 1 1 1 1 3
1 4 1 1 2 1 1 2 2 3 1 6 3 6 4 2 3 1 3 1 3 1 2 1 3 1 1 7 1 5 8 2 1 1 1 3 5 3 2 1
1 1 1 1 6 7 1 1 2 2 1 1 2 1 6 11 2 1 1 1 1 1 1 13 3 1 5 1 1 2 8 1 1 1 1 1 4 1 1 1
10 1 12 1 1 1 7 10 2 1 23 1 1 1 5 8 3 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 1 9 1 1 1
2 1 1 1 1 9 3 1 1 2 3 1 1 2 1 1 1 7 1 1 2 1 1 1 2 1 1 1 2 2 1 1 2 1 2 2 1 2 1 17
1 5 1 1 1 1 1 1 1 1 2 6 1 1 3 1 1 1 1 6 1 1 1 1 1 2 1 1 2 1 3 3 1 1 2 1 2 1 1 1
2 1 1 1 1 2 1 2 1 1 2 1 2 1 1 5 1 1 1 4 2 2 2 1 1 2 30 4 2 2 1 2 1 1 1 1 1 1 5 1
1 2 1 1 6 1 3 1 3 1 1 1 8 1 1 1 1 1 1 1 2 1 1 1 2 1 1 4 1 1 2 1 10 9 7 7 1 1 2 1
1 1 1 1 2 1 3 2 12 1 6 1 1 1 4 3 1 1 1 1 1 1 1 1 1 1 2 2 1 4 1 1 2 1 7 1 1 2 1 3
15 1 1 1 1 2 1 6 1 1 1 2 3 1 1 1 1 4 7 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 2 2 2
1 4 1 2 1 2 1 2 2 2 1 3 1 1 2 1 2 1 1 3 1 1 1 1 1 1 14 1 1 2 3 2 1 2 1 2 3 2 1 1
2 5 1 3 1 1 1 1 1 2 2 1 9 1 1 4 1 1 2 3 3 1 1 1 2 11 1 1 2 2 1 2 1 1 1 2 1 1 2 1
1 1 2 1 1 13 1 5 1 1 1 1 1 18 2 1 1 1 1 2 2 1 1 6 1 1 1 1 4 1 2 1 1 3 3 1 1 3 1 3
2 1 1 7 1 2 1 1 1 1 3 2 1 7 1 1 1 1 1 1 2 1 1 1 1 1 5 1 14 2 1 1 2 1 2 1 1 1 2 1
2 1 3 1 2 1 1 1 15 13 1 1 1 12 6 1 2 2 1 6 5 1 2 1 3 1 9 1 2 1 3 1 19 1 1 1 1 7 9 1
8 3 3 2 1 1 1 9 1 1 2 1 1 1 3 1 2 1 1 1 21 2 8 1 1 21 1 3 3 4 2 1 2 6 1 1 9 1 1 1
3 1 1 1 8 2 2 2 1 2 1 5 1 8 7 1 1 2 1 1 3 2 10 1 6 7 2 8 1 4 2 1 1 1 1 1 2 1 3 2
1 4 1 1 3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 7 4 8 1 5 17 2 1 2 1 1 1 1 1 1 1 2 2 1 3 1
1 2 2 9 1 1 1 1 3 1 1 2 1 1 7 28 1 5 1 1 1 2 1 2 3 1 2 1 1 1 1 1 2 1 1 1 3 1 3 1
1 1 1 3 1 19 4 1 1 1 2 1 5 1 1 1 1 1 1 2 2 1 3 1 1 1 5 2 2 1 3 1 1 3 1 1 1 1 1 1
1 2 1 1 1 4 1 1 1 4 3 4 1 2 1 3 1 10 1 1 6 2 1 1 1 1 1 1 1 6 2 1 4 2 8 1 5 2 1 1
1 1 1 1 4 1 4 1 1 1 7 1 1 3 30 1 3 1 1 3 1 1 3 2 1 1 1 6 1 1 1 1 1 1 1 2 11 1 1 1
1 1 2 1 1 3 28 5 1 1 1 1 1 1 1 3 11 1 4 1 2 1 1 4 1 6 2 1 1 1 1 1 26 1 1 7 1 2 2 2
2 1 10 1 1 1 2 1 1 2 1 2 1 1 1 1 1 1 1 2 2 3 1 1 1 1 1 1 3 1 4 2 2 1 1 11 4 1 4 5
1 1 1 2 6 17 2 1 4 22 1 9 1 11 25 3 2 1 1 1 2 7 1 2 2 1 2 16 1 2 1 1 3 1 5 3 1 1 1 1
1 1 3 6 1 3 1 4 6 1 3 4 4 1 1 1 2 1 1 1 1 5 1 6 7 1 1 1 1 1 1 1 3 1 2 1 1 1 1 4
3 1 1 1 1 9 1 1 1 1 1 3 1 4 3 1 1 1 4 1 2 1 2 7 1 4 1 1 1 1 3 1 1 1 8 1 1 1 1 1
1 1 2 1 7 2 1 4 1 1 1 3 1 1 1 2 1 6 1 1 1 2 23 4 1 1 1 1 1 1 10 1 1 1 1 1 15 14 1 1
2 1 1 1 2 1 1 5 1 12 17 1 1 1 1 1 1 3 1 1 1 1 1 1 1 7 1 2 1 1 5 4 1 1 1 7 1 3 1 1
2 1 1 1 2 3 2 2 1 1 8 2 1 2 2 2 1 1 2 1 1 1 1 6 1 5 1 1 1 1 1 1 1 3 1 1 1 7 1 2
该保护套包含在测试仪中。 与 input_0.txt 相同。性能越高,出现频率越低。
省略输出示例。

关于分配

我们通过以下链接提供测试用例生成器、测试器、示例输入数据和可视化器。

测试用例生成器、测试器、示例输入数据、可视化工具 (zip)


展示台说明

我们准备了一个可视化工具,可以可视化分数计算以及输入和输出文件的结果。

  • 该可视化工具是桌面版本 谷歌浏览器 和 Mozilla 火狐浏览器 已在最新版本的 上确认操作。我们不保证它适用于所有浏览器环境。
  • 此可视化工具上计算的分数不是本次比赛的分数。评分将通过在 AtCoder 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
  • 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。

可视化工具也包含在发行版中,发行版中的 README.html 中描述了如何使用它。

输入文件
输出文件
分数 $$$v$$$ 的
另存为图像