Background

Translated from Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection) D1T3. $\texttt{3s,0.5G}$.

Problem Description

Peppers are planted in a garden. The garden can be described as an $(N+1)\times (M+1)$ grid graph, where the peppers are planted on the grid points. She also uses $[(N+1)\times (M+1)-1]$ ropes to connect adjacent grid points, so that any two pepper plants can reach each other through the ropes. In other words, the ropes form the edges of a spanning tree of this grid graph.

Define two pepper plants to be connected if and only if they are directly or indirectly connected by ropes.

At night, someone will come to sabotage. The saboteur will make one straight cut either horizontally or vertically, cutting all ropes that the cut passes through. After the cut, the pepper plants will be split into several connected components. The saboteur will try to maximize the number of connected components.

How should you arrange the ropes so that, after the cut, the number of connected components is as small as possible?

Input Format

One line with two positive integers $N, M$.

Output Format

Output $(2N+1)$ lines, each containing $(3M+1)$ characters.

Among them, in line $(2i-1)$, the $(3j-2)$-th character represents the point $(i,j)$ (the plant in row $i$, column $j$), denoted by o (ASCII 111).

For two points $(i,j)$ and $(i,j+1)$ in the same row, if there is an edge, fill the two spaces between them with -- (ASCII 45); otherwise, do not fill them.

For two points $(i,j)$ and $(i+1,j)$ in the same column, if there is an edge, fill the one space between them with | (ASCII 124); otherwise, do not fill it.

All unfilled areas should be padded with spaces. Do not output extra spaces or extra blank lines.

You may refer to the sample output.

2 2

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

2 2

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

Hint

Scoring

If your output is an optimal solution, you get full score for that test point.

Otherwise, the score multiplier is computed as follows:

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

Where $A$ is the optimal answer, and $B$ is the answer of your construction.

You will get $K$ times the score of that test point. The subtask score is the minimum score among the test points in that subtask.

For example, Sample 1 gets full score. Sample 2 gets $75\%$ of the score.

Constraints

For $100\%$ of the data, it is guaranteed that $1\le N\le M\le 1\, 000$.

Subtask ID	$N, M\le$	Special Property	Score
$1$	$1\,000$	A	$15$
$2$		B
$3$	$3$		$5$
$4$	$10$		$10$
$5$	$100$		$20$
$6$	$1\, 000$		$35$

• Special Property A: $N=M$.
• Special Property B: $2N=M$.

Translated by ChatGPT 5