← 返回题目列表

AtCoder · abc345_d

G. 平铺

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

有一个网格 H 行和 W 列,每个单元格的边长为 1,我们有 N 瓷砖。
的 i第一个图块 (1\leq i\leq N) 是一个大小为的矩形 A_i\times B_i.
确定是否可以将图块放置在网格上,以便满足以下所有条件:

  • 每个单元格都被一块瓷砖覆盖。
  • 拥有未使用的瓷砖很好。
  • 瓷砖 放置时可能会旋转或翻转。但是,每个图块必须与单元格的边缘对齐,而不能延伸到网格之外。

约束

  • 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
\ldots
A_N B_N

输出

如果可以将图块放置在网格上以满足问题陈述中的所有条件,请打印 Yes;否则,打印 No.


样本输入 1

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

示例输出 1

Yes

放置 2-nd, 4-th,以及 5如下所示的第一个图块正好覆盖了网格的每个单元格一个图块。

因此,打印 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

请注意,每个单元格必须恰好被一个图块覆盖。