問題一覧 > 通常問題

No.3744 XY Tiling

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 7
作問者 : 👑 kencho / テスター : uruzunyaa
お気に入りにしたユーザー ProblemId : 13764 / 自分の提出
問題文最終更新日: 2026-11-02 04:30:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
グリッド構築24題 (順位表) の他の問題:

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.

SubtaskScoreConstraints
部分点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もしくは右上の雲マークをクリックしてアカウントを作成してください。