102893: [Atcoder]ABC289 D - Step Up Robot
Description
Score : $400$ points
Problem Statement
There is a staircase with infinite steps. The foot of the stairs is the $0$-th step, the next step is the $1$-st step, the next is the $2$-nd, and so on.
There is a stair-climbing robot on the $0$-th step. The robot can climb up $A _ 1,A _ 2,\ldots$, or $A _ N$ steps at a time. In other words, when the robot is on the $i$-th step, it can step onto one of the $(i+A _ 1)$-th step, $(i+A _ 2)$-th step, $\ldots$, and $(i+A _ N)$-th step, but not onto the others in a single step. The robot cannot descend the stairs, either.
There are traps on the $B _ 1$-th, $B _ 2$-th, $\ldots$, and $B _ M$-th steps. Once the robot steps onto a step with a trap, it cannot move anymore.
The robot wants to step onto the $X$-th step. Determine whether it is possible to do so.
Constraints
- $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$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A _ 1$ $A _ 2$ $\ldots$ $A _ N$ $M$ $B _ 1$ $B _ 2$ $\ldots$ $B _ M$ $X$
Output
In a single line, print Yes
if the robot can step onto the $X$-th step, and No
otherwise.
Sample Input 1
3 3 4 5 4 4 5 6 8 15
Sample Output 1
Yes
For example, the robot can reach the $15$-th step as follows.
- Climb up $3$ steps. The robot is now on the $3$-rd step.
- Climb up $4$ steps. The robot is now on the $7$-th step.
- Climb up $5$ steps. The robot is now on the $12$-th step.
- Climb up $3$ steps. The robot is now on the $15$-th step.
Sample Input 2
4 2 3 4 5 4 3 4 5 6 8
Sample Output 2
No
No matter how the robot moves, it cannot step onto the $8$-th step.
Sample Input 3
4 2 5 7 8 5 2 9 10 11 19 20
Sample Output 3
Yes
Input
题意翻译
有一机器人初始在 $0$ 级阶梯,对于每一级阶梯,机器人可以从 $1\sim N$ 种任选一个 $i$ 走 $A_i$ 步,同时有 $M$ 个障碍在 $B_i$ 级阶梯,若走到障碍则将无法移动,问能否通过某种方案使机器人到达第 $X$ 级阶梯。 $1\leq N\leq 10$,$1\leq M\leq 10^5$,$1\leq X\leq 10^5$,$A_i$ 和 $B_i$ 严格单调递增,$\forall i\in [1,M],B_i\neq X$。Output
问题描述
有一个无限级的楼梯。楼梯的底部是第0级台阶,下一个台阶是第1级台阶,再下一个台阶是第2级台阶,以此类推。
有一个楼梯攀爬机器人在第0级台阶上。机器人可以一次爬升A1、A2、……或AN级台阶。也就是说,当机器人在第i级台阶时,它可以一步跳到第(i+A1)级台阶、第(i+A2)级台阶、……和第(i+AN)级台阶,但不能一步跳到其他台阶。机器人也不能向下走台阶。
在第B1级、B2级、……和BM级台阶上都有陷阱。一旦机器人踏上一个有陷阱的台阶,它就无法再移动了。
机器人想要踏上第X级台阶。确定是否可以做到这一点。
约束
- 1≤N≤10
- 1≤A1<A2<……<AN≤105
- 1≤M≤105
- 1≤B1<B2<……<BM<X≤105
- 输入中的所有值都是整数。
输入
输入从标准输入中给出,格式如下:
$N$ $A _ 1$ $A _ 2$ $\ldots$ $A _ N$ $M$ $B _ 1$ $B _ 2$ $\ldots$ $B _ M$ $X$
输出
在一行中,如果机器人可以踏上第X级台阶,则打印Yes
,否则打印No
。
样例输入1
3 3 4 5 4 4 5 6 8 15
样例输出1
Yes
例如,机器人可以按以下方式到达第15级台阶:
- 爬升3级台阶。机器人现在在第3级台阶上。
- 爬升4级台阶。机器人现在在第7级台阶上。
- 爬升5级台阶。机器人现在在第12级台阶上。
- 爬升3级台阶。机器人现在在第15级台阶上。
样例输入2
4 2 3 4 5 4 3 4 5 6 8
样例输出2
No
无论机器人如何移动,它都无法踏上第8级台阶。
样例输入3
4 2 5 7 8 5 2 9 10 11 19 20
样例输出3
Yes