Step Up Robot

题目描述

有一座有无限台阶的楼梯。 楼梯底端是第 $0$ 阶，下一阶是第 $1$ 阶，再下一阶是第 $2$ 阶，依此类推。 有一个爬楼机器人在第 $0$ 阶。 机器人一次可以向上爬 $A _ 1,A _ 2,\ldots$ 或 $A _ N$ 阶。 换句话说，当机器人在第 $i$ 阶时，它可以踏到第 $(i+A _ 1)$ 阶、第 $(i+A _ 2)$ 阶、$\ldots$ 和第 $(i+A _ N)$ 阶中的一个， 但不能在一步之内踏到其他阶。 机器人也不能向下走楼梯。 在第 $B _ 1$ 阶、第 $B _ 2$ 阶、$\ldots$ 和第 $B _ M$ 阶有陷阱。 一旦机器人踏到有陷阱的阶上，就不能再移动。 机器人想踏到第 $X$ 阶。 判断是否有可能做到这一点。

输入格式

输入从标准输入给出，格式如下： $N$ $A _ 1$ $A _ 2$ $\ldots$ $A _ N$ $M$ $B _ 1$ $B _ 2$ $\ldots$ $B _ M$ $X$

输出格式

如果机器人可以踏到第 $X$ 阶，输出一行包含 $Yes$，否则输出 $No$。

3
3 4 5
4
4 5 6 8
15

Yes

4
2 3 4 5
4
3 4 5 6
8

No

4
2 5 7 8
5
2 9 10 11 19
20

Yes

提示

$1\leq N\leq10$ $1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5$ $1\leq M\leq10^5$ $1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5$ 输入中的所有数值均为整数。例如，机器人可以按如下方式到达第 $15$ 阶。

爬上 $3$ 阶。 机器人现在位于第 $3$ 阶。 爬上 $4$ 阶。 机器人现在位于第 $7$ 阶。 爬上 $5$ 阶。 机器人现在位于第 $12$ 阶。 爬上 $3$ 阶。 机器人现在位于第 $15$ 阶。
无论机器人如何移动，都无法踏到第 $8$ 阶。

标签: AtCoder|abc289D

来源

AtCoder|abc289D