← 返回题目列表

AtCoder · abc318_f

I. 章鱼

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

分数: 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 满足条件。