Octopus

题目描述

有一只章鱼形状的机器人，以及一条数轴上的 $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$，则任选一个这样的宝物并抓取它。

输入格式

输入由标准输入按如下格式给出： $N$ $X_1$ $X_2$ $\ldots$ $X_N$ $L_1$ $L_2$ $\ldots$ $L_N$

输出格式

输出满足题目条件的整数 $k$ 的个数。

3
-6 0 7
3 5 10

6

1
0
1000000000000000000

2000000000000000001

2
-100 100
1 1

0

提示

$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}$ 所有输入值均为整数。$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$ 的宝物。
所有从 $-10^{18}$ 到 $10^{18}$ 的整数 $k$ 都满足条件。
没有 $k$ 满足条件。

标签: AtCoder|abc318F

来源

AtCoder|abc318F