/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
縦 H 行、横 W 列のグリッドがあって、上から i 番目、左から j 番目のマスを (i,j) と表すことにします。 グリッドは (r,c) のマスだけに穴が空いています。穴が空いていないマス全体を何枚かのタイルで敷き詰めます。H \times W=L \times (N+M)+1 を満たす非負整数 N,M が与えられます。
縦 1 行、横 L 列のタイルを横長タイル、縦 L 行、横 1 列のタイルを縦長タイルと呼ぶことにします。
横長タイル N 枚と縦長タイル M 枚を回転させないまま使う敷き詰め方が存在するかを判定し、存在するなら敷き詰め方も示してください。
出力方法やより厳密な条件についての詳細は出力セクションを確認してください。
1 つの入力ファイルにつき、T 個のテストケースを解いてください。
制約
- 1 \leq T \leq 5
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- 2 \leq H \times W
- 2 \leq L \leq 1000
- 0 \leq N
- 0 \leq M
- 1 \leq r \leq H
- 1 \leq c \leq W
- H \times W=L \times (N+M)+1
- 全てのテストケースにおける N+M の総和は 6\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T case_1 case_2 \vdots case_T
各ケースは以下の形式で与えられる。
H W L N M r c
出力
答えを以下の形式で出力せよ。
output_1 output_2 \vdots output_T
ここで、output_t は t 番目のテストケースへの出力を表す。
各ケースでは、条件を満たすように敷き詰めることが可能ならば、i 枚目の横長タイルが覆うマスのうち最も左にあるマスを (A_i,B_i)、j 枚目の縦長タイルが覆うマスのうち最も上にあるマスを (C_j,D_j) として、以下の形式で出力せよ。
Yes A_1 B_1 A_2 B_2 \vdots A_N B_N C_1 D_1 C_2 D_2 \vdots C_M D_M
より厳密には、以下の条件を全て満たす長さ N の整数列 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N) と長さ M の整数列 C=(C_1,C_2,\dots,C_M),D=(D_1,D_2,\dots,D_M) を出力せよ。
- \{(A_i,B_i+l)\mid i=1,2,\dots,N,\;l=0,1,\dots,L-1\} と \{(C_j+l,D_j)\mid j=1,2,\dots,M,\;l=0,1,\dots,L-1\} と \{(r,c)\} の和集合が、\{(h,w)\mid h=1,2,\dots,H,\;w=1,2,\dots,W\} に等しい。
なお、H \times W=L \times (N+M)+1 という制約より、この条件が成り立つとき、タイル同士が重なることはない。
条件を満たすことが不可能ならば No を出力せよ。
入力例 1
3 1 3 2 1 0 1 1 1 3 2 1 0 1 2 3 3 2 1 3 1 1
出力例 1
Yes 1 2 No Yes 3 2 2 1 1 2 1 3
3 つ目のテストケースでは、最も左上のマスに穴が空いています。以下のように敷き詰めることができます。
┌─┬─┐ ┌─┤ │ │ │ ├─┴─┤ └─┴───┘
Score : 800 points
Problem Statement
There is a grid with H rows and W columns, where the cell at the i-th row from the top and j-th column from the left is denoted as (i,j). The grid has a hole only in cell (r,c). We will tile all cells without a hole using several tiles. You are given non-negative integers N and M such that H \times W=L \times (N+M)+1. A tile of 1 row and L columns is called a horizontal tile, and a tile of L rows and 1 column is called a vertical tile. Determine whether there exists a way to tile using exactly N horizontal tiles and M vertical tiles without rotation, and also show one such way if it exists. For details on the output format and more precise conditions, check the output section.
Solve T test cases for each input file.
Constraints
- 1 \leq T \leq 5
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- 2 \leq H \times W
- 2 \leq L \leq 1000
- 0 \leq N
- 0 \leq M
- 1 \leq r \leq H
- 1 \leq c \leq W
- H \times W=L \times (N+M)+1
- The sum of N+M over all test cases is at most 6\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is given in the following format:
H W L N M r c
Output
Output the answers in the following format:
output_1 output_2 \vdots output_T
Here, output_t represents the output for the t-th test case.
For each case, if it is possible to tile satisfying the conditions, let (A_i,B_i) be the leftmost cell covered by the i-th horizontal tile and (C_j,D_j) be the topmost cell covered by the j-th vertical tile, and output in the following format:
Yes A_1 B_1 A_2 B_2 \vdots A_N B_N C_1 D_1 C_2 D_2 \vdots C_M D_M
More precisely, output integer sequences A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N) of length N and C=(C_1,C_2,\dots,C_M),D=(D_1,D_2,\dots,D_M) of length M that satisfy all of the following conditions:
- The union of \{(A_i,B_i+l)\mid i=1,2,\dots,N,\;l=0,1,\dots,L-1\}, \{(C_j+l,D_j)\mid j=1,2,\dots,M,\;l=0,1,\dots,L-1\}, and \{(r,c)\} equals \{(h,w)\mid h=1,2,\dots,H,\;w=1,2,\dots,W\}.
Note that due to the constraint H \times W=L \times (N+M)+1, when this condition holds, tiles do not overlap with each other.
If it is impossible to satisfy the conditions, output No.
Sample Input 1
3 1 3 2 1 0 1 1 1 3 2 1 0 1 2 3 3 2 1 3 1 1
Sample Output 1
Yes 1 2 No Yes 3 2 2 1 1 2 1 3
In the third test case, there is a hole in the top-left cell. It can be tiled as follows:
┌─┬─┐ ┌─┤ │ │ │ ├─┴─┤ └─┴───┘