最高分数:1500 点
问题陈述
2022年6月20日是AtCoder上线10周年纪念日。
这一天,AtCoder 前面建了一个花园来庆祝这个周年纪念日。
花园被表示为 H \times W 网格。该细胞 i从顶部开始的第行和 j从左边算起的第列表示为单元格 (i, j).
每个单元格中都有一朵花。细胞里的花之美 (i, j) is A_{i, j}.
花园的例子如下:(案例 H = 4, W = 5)
你应该做一个 美丽的花园 通过在某些细胞中切花。一个美丽的花园应满足以下条件:
- 对于所有 a, b, c, d 细胞中都开花 (a, b) 和细胞 (c, d) ((a, b) \neq (c, d)) 尚未被切割,它满足以下条件。
- 来自 (a, b) to (c, d),正好有 1 种方法可以走,即向上、向右、向左、向下重复移动一格,而不经过同一个单元格两次。
例如,如果你剪了一些花,比如 A,和 B,这将是 美丽的花园.
例如,如果你剪了一些花,比如 C, D, E,它不会是 美丽的花园.
的 花园评分 将计算如下:
- 如果花园不是 美丽的花园,分数将为 0.
- 如果花园是 美丽的花园,分数将为未修剪的花朵的总美感。
例如花园的分数 A is 20,花园得分 B is 60,以及花园的得分 C, D, E 是 0.
打印一种切花的方法 花园评分 尽可能高。
输入
输入由标准输入按以下格式给出:
H W
A_{1, 1} A_{1, 2} A_{1, 3} ... A_{1, W}
A_{2, 1} A_{2, 2} A_{2, 3} ... A_{2, W}
A_{3, 1} A_{3, 2} A_{3, 3} ... A_{3, W}
...
A_{H, 1} A_{H, 2} A_{H, 3} ... A_{H, W}
输出
打印 H 喜欢如下:
c_{1, 1}c_{1, 2}c_{1, 3} ... c_{1, W}
c_{2, 1}c_{2, 2}c_{2, 3} ... c_{2, W}
c_{3, 1}c_{3, 2}c_{3, 3} ... c_{3, W}
...
c_{H, 1}c_{H, 2}c_{H, 3} ... c_{H, W}
c_{i, j} 应该是 # 如果你 不会 在单元格中剪一朵花 (i, j),和 . 如果你 将 细胞中的切花 (i, j).
约束
- H, W 是介于 1 和 500.
- A_{i, j} 是介于 1 和 9.
关于测试用例
测试用例生成如下:
- 对于每个测试用例, H, W 已确定。您应该查看子任务/评分部分以了解确切的值。
- A_{i, j} 是之间的随机整数 1 和 9。的概率 A_{i, j} = 1 is 1 in 9。对于 A_{i, j} = 2, 3, 4, ..., 9.
子任务和评分
有 15 用于评分的测试用例。由于每种情况的最大分数是 100。该问题的最高分是 100 \times 15 = 1500.
对于每种情况,评分如下。 L 是输出中花园的分数,让 L' be L \div (H \times W).
(i) 当 H = 5, W = 5 (案例#1、#2、#3),或 H = 5, W = 500 (案例#4、#5、#6):
- If 0.00 \leq L' < 2.00 : 0 点
- If 2.00 \leq L' < 3.33 : 0 + (L - 2.00) \times 21 点
- If 3.33 \leq L' < 3.93 : 28 + (L - 3.33) \times 40 点
- If 3.93 \leq L' < 4.03 : 52 + (L - 3.93) \times 480 点
- If 4.03 \leq L' : 100 点
(ii) 当 H = 500, W = 500 (案例#7、#8、#9、#10、#11、#12、#13、#14、#15):
- If 0.00 \leq L' < 2.00 : 0 点
- If 2.00 \leq L' < 3.33 : 0 + (L - 2.00) \times 21 点
- If 3.33 \leq L' < 3.78 : 28 + (L - 3.33) \times 75 点
- If 3.78 \leq L' < 3.84 : 61 + (L - 3.78) \times 650 点
- If 3.84 \leq L' : 100 点
这是描述之间关系的图表 L' 并得分 2.00 \leq L' \leq 4.05.
注意
判决将是 AC 如果没有已评分的测试用例 0 点。
这意味着如果你得到了,它并不总是满分 AC,这也意味着即使你得到了 WA 您可能获得了部分分数。
由于这个问题是类似马拉松比赛的优化任务,因此不能保证所有情况都有完整的解决方案。问题解决者的解决方案并不总是满分。 另外,这种情况不太可能发生,但如果很多人写出的解法大大超过了满分的标准,改变评分公式也是可能的。保证评分公式不发生变化 3 距离本次比赛开始的小时数。
示例输入 1
3 3 1 2 3 4 5 6 7 8 9
示例输出 1
#.# ### #.#
在这个例子中,花园的得分是 1 + 3 + 4 + 5 + 6 + 7 + 9 = 35.
注意:此输入不包含在评分数据集中。
示例输入 2
4 5 4 1 8 2 6 2 2 1 2 5 3 5 1 9 2 5 1 2 3 6
示例输出 2
#.### #...# ##### #.#.#
这个例子与问题陈述中写的示例图片相同。
此外,此示例输出与花园相同 B 写在问题陈述中。花园得分为 60,以及值 L' is 3.0.
其实有一个解,花园的分数是 62 :)
注意:此输入也不包含在评分数据集中。