QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

#12166. 幼苗

Statistics

Malnar 先生在 2018 年 3 月末从当地的家庭农场带回了一堆辣椒。他轻松地用绳子将它们以最优的方式连接起来,并无私地分给了朋友们。第一个品尝的是 Dominik,他甚至没感觉到辣味,接着是 Josip,以此类推。然而,Malnar 先生的一些朋友被辣得够呛。其中值得一提的是 Krešimir,他发誓要报复 Malnar 先生。

如今,Malnar 先生不再购买辣椒,而是自己种植。今年,他决定在坐标系中种植 $(N + 1) \cdot (M + 1)$ 株幼苗,使它们位于集合 $\{0, 1, 2, \dots, N\} \times \{0, 1, 2, \dots, M\}$ 的整点上。此外,他决定使用 $(N + 1)(M + 1) - 1$ 段单位长度的绳子将幼苗连接起来,即如果两株幼苗的欧几里得距离为 1,则可以用一段绳子直接连接。此外,幼苗必须连接成一个连通块(即“花环”)。我们称两株幼苗属于同一个花环,如果一只微小的蚂蚁仅通过幼苗和绳子就能在它们之间爬行。

当 $N = 1$ 且 $M = 2$ 时,幼苗连接方式的示例。

Malnar 先生知道 Krešimir 想破坏他的计划。他预感到 Krešimir 会在夜幕掩护下潜入,并进行恰好一次水平或垂直的切割,切断路径上遇到的每一段绳子。已知 Krešimir 不会伤害幼苗本身,但他的切割方式会使初始的花环尽可能多地分裂成多个花环。

因此,Malnar 先生希望以一种方式连接幼苗,使得在 Krešimir 切割后,剩余花环的数量尽可能少。

你能确定一种 Malnar 先生连接幼苗的方式吗?

输入格式

第一行包含自然数 $N$ 和 $M$。

输出格式

输出 $2N + 1$ 行,每行 $3M + 1$ 个字符,表示幼苗通过绳子连接的方式。

幼苗用字符 'o' (ASCII 111) 表示,连接同一列中两株幼苗的绳子用字符 '|' (ASCII 124) 表示,连接同一行中两株幼苗的绳子用字符 '--' (ASCII 45) 表示。

相邻但未被绳子连接的幼苗之间用空格隔开,同一行中相邻幼苗间有两个空格 (ASCII 32),同一列中相邻幼苗间有一个空格 (ASCII 32)。

子任务

对于未能达到最优解的方案,得分计算公式如下:

$$0.75 \cdot \max \left( \left( \frac{A - 1}{B - 1} \right)^4, 1 - \left( 1 - \frac{1}{(B - A)^2} \right)^6 \right) \cdot X$$

其中 $A$ 表示最优解中 Krešimir 切割后的花环数量,$B$ 表示你的方案中对应的数量,$X$ 为该测试点预设的分数。

子任务得分等于该子任务中所有测试点得分的最小值。

子任务 分数 数据范围
1 15 $1 \le N = M \le 1000$
2 15 $2 \le 2N = M \le 1000$
3 5 $1 \le N \le M \le 3$
4 10 $1 \le N \le M \le 10$
5 20 $1 \le N \le M \le 100$
6 35 $1 \le N \le M \le 1000$

样例

输入 1

2 2

输出 1

o--o o
|  |
o o--o
|  |
o--o--o

输入 2

2 2

输出 2

o--o--o
|
o o--o
|  |
o--o--o

说明

第一个样例的输出代表了一种最优的连接方式。Krešimir 的切割会将这个花环拆分成三个较小的花环。

第二个样例的输出代表了一种 Malnar 先生最初想到的次优连接方式(注意字母 G 的形状)。Krešimir 的切割会将这个花环拆分成四个较小的花环。对于这种输出,你将获得该测试点总分的 75%。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.