103185: [Atcoder]ABC318 F - Octopus

Problem Statement

There is an octopus-shaped robot and $N$ treasures on a number line. The $i$-th treasure $(1\leq i\leq N)$ is located at coordinate $X_i$.
The robot has one head and $N$ legs, and the $i$-th leg $(1\leq i\leq N)$ has a length of $L_i$.

Find the number of integers $k$ such that the robot can grab all $N$ treasures as follows.

• Place the head at coordinate $k$.
• Repeat the following for $i=1,2,\ldots,N$ in this order: if there is a treasure that has not been grabbed yet within a distance of $L_i$ from the head, that is, at a coordinate $x$ satisfying $k-L_i\leq x\leq k+L_i$, choose one such treasure and grab it.

Constraints

• $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}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$X_1$ $X_2$ $\ldots$ $X_N$
$L_1$ $L_2$ $\ldots$ $L_N$

Output

Print the number of integers $k$ that satisfy the condition in the statement.

Sample Input 1

3
-6 0 7
3 5 10

Sample Output 1

6

$k=-3,-2,-1,2,3,4$ satisfy the condition. For example, when $k=-3$, the robot can grab all three treasures as follows.

• The first leg can grab treasures at coordinates $x$ satisfying $-6\leq x\leq 0$. Among them, grab the first treasure at coordinate $-6$.
• The second leg can grab treasures at coordinates $x$ satisfying $-8\leq x\leq 2$. Among them, grab the second treasure at coordinate $0$.
• The third leg can grab treasures at coordinates $x$ satisfying $-13\leq x\leq 7$. Among them, grab the third treasure at coordinate $7$.

Sample Input 2

1
0
1000000000000000000

Sample Output 2

2000000000000000001

All integers $k$ from $-10^{18}$ to $10^{18}$ satisfy the condition.

Sample Input 3

2
-100 100
1 1

Sample Output 3

0

No $k$ satisfies the conditions.

问题描述

有一个章鱼形状的机器人和$N$个宝藏在一个数轴上。 第$i$个宝藏$(1\leq i\leq N)$位于坐标$X_i$。
机器人有一个头和$N$条腿，第$i$条腿$(1\leq i\leq N)$的长度为$L_i$。

找出满足以下条件的整数$k$的数量。

• 将头放在坐标$k$处。
• 按照以下顺序重复操作$i=1,2,\ldots,N$：如果头部附近还有未抓取的宝藏，即在距离头部$L_i$的范围内，满足$k-L_i\leq x\leq k+L_i$的坐标$x$处有一个宝藏，选择一个这样的宝藏并抓住它。

约束条件

• $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

从$-10^{18}$到$10^{18}$的所有整数$k$都满足条件。

样例输入3

2
-100 100
1 1

样例输出3

0

没有$k$满足条件。