C - Square Corner Packing 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

H 行 W 列のマス目があります。 上から i 行目、左から j 列目のマスを (i,j) と表します。 はじめ、全てのマスは白です。

以下の操作を好きな回数行います。

  • 以下の条件を全て満たす整数 r,c,s を選び、マス (r,c),(r+s,c),(r,c+s),(r+s,c+s) を黒く塗る。

    • 1\le r<r+s\le H
    • 1\le c<c+s\le W
    • マス (r,c),(r+s,c),(r,c+s),(r+s,c+s) が全て白。

行うことができる操作回数の最大値を求め、その最大値を達成する操作列を 1 つ出力してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\le T\le 500
  • 2\le H,W\le 500
  • 全てのテストケースにおける HW の総和は 250000 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

H W

出力

各テストケースについて、操作回数の最大値を K、i 回目の操作で選ぶ整数を r_i,c_i,s_i とし、以下の形式で出力せよ。

K
r_1 c_1 s_1
r_2 c_2 s_2
\vdots
r_K c_K s_K

最大値を達成する操作列が複数存在する場合、どれを出力しても正解となる。

入力例 1

2
5 6
2 2

出力例 1

6
1 1 3
3 4 2
1 2 3
3 3 2
1 3 3
2 1 1
1
1 1 1

1 個目のテストケースについて、出力された 6 回の操作を行うと、黒く塗られるマスは以下のようになります。 数字 i は i 回目の操作で黒く塗られるマスを表し、. は最後まで塗られないマスを表します。

135135
66....
664242
135135
..4242

この出力以外にも正解となる出力は存在します。

Score : 700 points

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left. Initially, all cells are white.

You may perform the following operation any number of times.

  • Choose integers r,c,s satisfying all of the following conditions, and paint the cells (r,c),(r+s,c),(r,c+s),(r+s,c+s) black.

    • 1\le r<r+s\le H
    • 1\le c<c+s\le W
    • The cells (r,c),(r+s,c),(r,c+s),(r+s,c+s) are all white.

Find the maximum number of operations you can perform, and output one sequence of operations that achieves that maximum.

You are given T test cases; solve each of them.

Constraints

  • 1\le T\le 500
  • 2\le H,W\le 500
  • The sum of HW over all test cases is at most 250000.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

H W

Output

For each test case, let K be the maximum possible number of operations, and let r_i,c_i,s_i be the integers chosen in the i-th operation; output them in the following format:

K
r_1 c_1 s_1
r_2 c_2 s_2
\vdots
r_K c_K s_K

If there are multiple sequences of operations that achieve the maximum, any of them will be accepted.

Sample Input 1

2
5 6
2 2

Sample Output 1

6
1 1 3
3 4 2
1 2 3
3 3 2
1 3 3
2 1 1
1
1 1 1

For the first test case, performing the six output operations paints the following cells black. The digit i represents a cell painted black by the i-th operation, and . represents a cell that is never painted.

135135
66....
664242
135135
..4242

There are other outputs that will be accepted.