Score : $575$ points

问题描述

在数轴上有一个章鱼形状的机器人和$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$，则选择其中一个这样的宝藏并抓取它。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 09:05:06