分数: 575 点
问题陈述
有一个章鱼形状的机器人, N 数轴上的宝藏。
的 i第一个宝藏 (1\leq i\leq N) 位于坐标 X_i.
机器人有一个头, N 腿,以及 i第一条腿 (1\leq i\leq N) 的长度为 L_i.
查找数量 整数 k 这样机器人就可以抓取所有 N 宝物如下。
- 将头部放置在坐标处 k.
- 重复以下操作 i=1,2,\ldots,N 按此顺序:如果在以下距离内有尚未抢夺的宝藏 L_i 从头部开始,即在某个坐标处 x 满意 k-L_i\leq x\leq k+L_i,选择一个这样的宝藏并抓住它。
约束
- 1 \leq N\leq 200
- -10^{18} \leq X_1<X_2<\cdots<X_N\leq 10^{18}
- 1\leq L_1\leq L_2\leq\cdots\leq L_N\leq 10^{18}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X_1 X_2 \ldots X_N L_1 L_2 \ldots L_N
输出
打印整数个数 k 满足语句中的条件。
示例输入 1
3 -6 0 7 3 5 10
示例输出 1
6
k=-3,-2,-1,2,3,4 满足条件。例如,当 k=-3,机器人可以抓取全部三个宝物,如下。
- 第一站可以在坐标处抢宝物 x 满意 -6\leq x\leq 0。其中,在坐标处抢第一个宝物 -6.
- 第二站可以在坐标处抢宝物 x 满意 -8\leq x\leq 2。其中,在坐标处抢第二个宝物 0.
- 第三条腿可以在坐标处抢宝物 x 满意 -13\leq x\leq 7。其中,在坐标处抢第三个宝物 7.
示例输入 2
1 0 1000000000000000000
示例输出 2
2000000000000000001
所有整数 k 来自 -10^{18} to 10^{18} 满足条件。
示例输入 3
2 -100 100 1 1
示例输出 3
0
No k 满足条件。