No.3744 XY Tiling
Problem Statement
You will create a colored grid by completely tiling an $H \times W$ rectangular grid with colored rectangular tiles of size $1 \times 2$ or $2 \times 1$. Find one example of a tiling that satisfies all of the following conditions and uses the minimum number of distinct colors.
- Every tile completely covers exactly $2$ cells of the grid
- Tiles must not extend outside the grid, and different tiles must not overlap
- The $2$ cells composing each tile are painted in different colors
- In the entire completed colored grid, the region painted in the same color is 4-connected
Here, the region painted in the same color being 4-connected means that for any $2$ cells $A, B$ painted in the same color $c$, it is possible to move from $A$ to $B$ passing only through cells painted in color $c$ that are adjacent vertically or horizontally.
It can be shown that such a tiling always exists under the constraints.
Constraints
- All inputs are integers
- $1 \leq H, W \leq 200$
- $HW$ is even
Partial Score
This problem has partial scoring based on subtasks.
| Subtask | Score | Constraints |
|---|---|---|
| 部分点 | 60% (300 pts) | $H,\ W$ は偶数 |
| 満点 | 40% (200 pts) | 追加の制約は無い |
Input
The input is given from standard input in the following format.
$H\ W$
Output
Output one example of a tiling that uses the minimum number of distinct colors, in the following format.
$C$
$x_{1, 1}\ y_{1, 1}\ c_{1, 1}\ x_{1, 2}\ y_{1, 2}\ c_{1, 2}$
$x_{2, 1}\ y_{2, 1}\ c_{2, 1}\ x_{2, 2}\ y_{2, 2}\ c_{2, 2}$
$\vdots$
$x_{\frac{HW}{2}, 1}\ y_{\frac{HW}{2}, 1}\ c_{\frac{HW}{2}, 1}\ x_{\frac{HW}{2}, 2}\ y_{\frac{HW}{2}, 2}\ c_{\frac{HW}{2}, 2}$
Here, $C$ is the number of distinct colors used. Denoting the cell in the $s$-th row from the top and the $t$-th from the left of the grid as $(s, t)$, the $2$ cells of the grid covered by the $i$-th tile are $(x_{i, 1}, y_{i, 1})$ and $(x_{i, 2}, y_{i, 2})$, and the colors of those $2$ cells are $c_{i, 1}$ and $c_{i, 2}$, respectively.
Note that $1 \leq c_{i, 1}, c_{i, 2} \leq C$ must hold, and each color from $1$ to $C$ must be painted on at least $1$ cell. The tiles may be output in any order.
Print a newline at the end.
Visualizer
A web-based visualizer for the output is available here.
During the contest, sharing visualization results and mentioning solutions or considerations are prohibited. Please be careful.
In principle, questions about the specifications of the visualizer will not be accepted. Please use it only as an auxiliary tool.
Sample
Sample 1
Input
2 2
Output
2 1 1 1 1 2 2 2 2 2 2 1 1
The tiling in the sample output is as shown in the following figure.
This case is included in the subtask cases.
The following output also satisfies the conditions of the problem, but it is not a correct answer because the number of distinct colors used is not the minimum.
3 1 1 3 1 2 2 2 2 2 2 1 1
Sample 2
Input
4 1
Output
3 1 1 2 2 1 1 3 1 1 4 1 3
The tiling in the sample output is as shown in the following figure.
For the regions painted in the same color to be connected, $3$ or more colors are required.
This case is not included in the subtask cases.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。