← 返回题目列表

AtCoder · tenka1_2014_qualB_d

D. 天下一艺术

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

問題文

天海一王国公主的命令,同为画家的智明被指派绘制长方形壁画。

但是,这项工作有两个问题。

  • 绘制壁画所用的涂料必须由公主指定。

    • 分配给公主的油漆都是不同的颜色。每个涂漆区域都涂有不同的颜色。
    • 每种油漆都有一个“厚度”。您可以覆盖“厚度”值低于该涂料的涂料,并用该涂料颜色覆盖它,但不应覆盖具有相同或更高值的涂料。
  • 智明君是世界上最笨的。

    • Tomoaki 只能绘制边与壁画的长度和宽度平行的矩形。
    • 您不能使用相同的油漆颜色两次。

为了以某种方式完成壁画,Tomoaki 首先创建了壁画的蓝图。

此蓝图是根据尺寸 它被分为 1 \times 1 方格,并为每个方格指定一个数字。

  • 每个方块的编号用于指定颜色编码。数字相同的方格必须涂成相同的颜色,数字不同的方格必须涂成不同的颜色。
  • 您可以使用正方形数字和油漆的任意组合。
  • 您不必使用所有油漆。
  • 所有方块必须至少绘制一次。

创作壁画不能失败的智明决定看看是否可以使用给他的颜料按照蓝图绘制壁画。


入力

N
A_1
A_2
:
A_N
H W
B_{1,1} B_{1,2} ... B_{1,W}
B_{2,1} B_{2,2} ... B_{2,W}
:
B_{H,1} B_{H,2} ... B_{H,W}
  • 第一行,一个整数,表示可用油漆的数量 N (1 \leq{} N \leq{} 17)。
  • 从第二行开始 N 行包含一个整数,表示每种涂料的暗度。 在 A_i (0 \leq{} A_i \leq{} 255)。
  • N+2 行中,一个整数表示蓝图的高度。 H (1 \leq{} H \leq{} 200)和一个表示蓝图宽度的整数。 W (1 \leq{} W \leq{} 200)。
  • N+3 从行 H 行给出了有关蓝图的信息。其中 y (1 \leq{} y \leq{} H) 每个方格的数字用空格分隔。 给出了 W 。y 从该行的左侧开始 x (1 \leq{} x \leq{} W)th,从蓝图顶部开始 y 正方形,从左起 x 方格位置的平方数,整数 如果 B_{y,x} (0 \leq{} B_{y,x} \leq{} N - 1)。

部分点

  • 1 \leq{} N \leq{} 5 和 所有满足 1 \leq{} H, W \leq{} 5中的所有测试用例都回答正确,则将获得35分作为部分分。 如果
  • 1 \leq{} N \leq{} 9 中的所有测试用例都回答正确,将额外获得40分作为部分分。

出力

如果可以用给定的涂料按照蓝图进行绘制,则输出1,否则输出0,一行。在输出末尾添加换行符。


入力例1

5
4
0
4
10
4
2 3
3 1 3
0 2 0

出力例1

1

如果给定的涂料从上到下是A、B、C、D、E,则可以按以下顺序进行涂装。

BBB
BBB
BBB
AAA
BCB
AAA
BCB
ADA

我在这个绘画方法中没有使用E。

入力例2

5
4
0
4
10
4
2 4
3 1 2 3
0 1 2 0

出力例2

0

您无法使用给定的涂料进行绘画。

入力例3

2
1
2
2 2
0 1
1 0

出力例3

0

您无法使用给定的涂料进行绘画。

入力例4

5
1
1
66
30
1
5 5
3 4 4 4 2
3 4 4 0 0
3 4 4 0 0
3 3 1 0 0
3 3 1 1 2

出力例4

1

如果给定的涂料从上到下是A、B、C、D、E,则可以按以下顺序进行涂装。

A A # # #
A A # # #
A A # # #
A A # # #
A A # # #
A A B B #
A A B B #
A A B B #
A A B B #
A A B B #
A A B B E
A A B B E
A A B B E
A A B B E
A A B B E
A D D D E
A D D D E
A D D D E
A A B B E
A A B B E
A D D D E
A D D C C
A D D C C
A A B C C
A A B B E