D - Tiling Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450 点

問題文

一辺の長さが 1 のマスからなる H 行 W 列のマス目と、N 枚のタイルがあります。
i (1\leq i\leq N) 枚目のタイルは A_i\times B_i の長方形です。
以下の条件をすべてみたすようにタイルをマス目に置くことができるか判定してください。

  • 全てのマスがちょうど 1 枚のタイルで覆われている。
  • 使用されないタイルがあっても良い。
  • 使用するタイルは 回転したり裏返したりして置かれていても良い。ただし、各タイルはマスの線に合わせてマス目からはみ出ることがないように置かれていなければならない。

制約

  • 1\leq N\leq 7
  • 1 \leq H,W \leq 10
  • 1\leq A_i,B_i\leq 10
  • 入力はすべて整数

入力

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

N H W
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

問題文中の条件をみたすようにタイルをマス目に置くことができるならば Yes を、そうでないならば No を出力せよ。

入力例 1

5 5 5
1 1
3 3
4 4
2 3
2 5

出力例 1

Yes

2,4,5 枚目のタイルを使用して次のように置くと、マス目の各マスをちょうど 1 枚のタイルで覆うことができます。

よって、Yes を出力します。

入力例 2

1 1 2
2 3

出力例 2

No

マス目からはみ出さないようにタイルを置くことはできません。
よって、No を出力します。

入力例 3

1 2 2
1 1

出力例 3

No

全てのマスを覆うようにタイルを置くことができません。
よって、No を出力します。

入力例 4

5 3 3
1 1
2 2
2 2
2 2
2 2

出力例 4

No

全てのマスはちょうど 1 枚のタイルで覆われている必要があることに注意してください。

Score: 450 points

Problem Statement

There is a grid of H rows and W columns, each cell having a side length of 1, and we have N tiles.
The i-th tile (1\leq i\leq N) is a rectangle of size A_i\times B_i.
Determine whether it is possible to place the tiles on the grid so that all of the following conditions are satisfied:

  • Every cell is covered by exactly one tile.
  • It is fine to have unused tiles.
  • The tiles may be rotated or flipped when placed. However, each tile must be aligned with the edges of the cells without extending outside the grid.

Constraints

  • 1\leq N\leq 7
  • 1 \leq H,W \leq 10
  • 1\leq A_i,B_i\leq 10
  • All input values are integers.

Input

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

N H W
A_1 B_1
A_2 B_2
\ldots
A_N B_N

Output

If it is possible to place the tiles on the grid so that all of the conditions in the problem statement are satisfied, print Yes; otherwise, print No.

Sample Input 1

5 5 5
1 1
3 3
4 4
2 3
2 5

Sample Output 1

Yes

Placing the 2-nd, 4-th, and 5-th tiles as shown below covers every cell of the grid by exactly one tile.

Hence, print Yes.

Sample Input 2

1 1 2
2 3

Sample Output 2

No

It is impossible to place the tile without letting it extend outside the grid.
Hence, print No.

Sample Input 3

1 2 2
1 1

Sample Output 3

No

It is impossible to cover all cells with the tile.
Hence, print No.

Sample Input 4

5 3 3
1 1
2 2
2 2
2 2
2 2

Sample Output 4

No

Note that each cell must be covered by exactly one tile.