← 返回题目列表

AtCoder · s8pc_6_i

I. 花园2

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

最高分数: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 :)
注意:此输入也不包含在评分数据集中。