AT_abc434_e [ABC434E] Distribute Bunnies
题目描述
有 $N$ 只编号为 $1$ 到 $N$ 的兔子站在数轴上。第 $i$ 只兔子站在坐标 $X_i$ 处,多个兔子可能站在同一个坐标上。
每只兔子有一个称为“跳跃力”的参数,第 $i$ 只兔子的跳跃力为 $R_i$。
现在,所有兔子各跳一次。当一只位于坐标 $x$,跳跃力为 $r$ 的兔子跳跃时,它可以跳到 $x+r$ 或 $x-r$ 的位置。
如果你可以自由选择每只兔子跳到哪个坐标,问所有兔子跳完后,最多能有多少个不同的坐标上有兔子。
输入格式
输入从标准输入读入,格式如下:
> $N$
> $X_1$ $R_1$
> $X_2$ $R_2$
> $\vdots$
> $X_N$ $R_N$
输出格式
输出一个整数,表示所有兔子跳跃后,最多可能有多少个不同的坐标上有兔子。
说明/提示
### 样例解释 1
如果每只兔子的跳跃方式如下,可以获得最大不同坐标数 $3$。
- 兔子 1 跳到 $4 - 1 = 3$。
- 兔子 2 跳到 $2 + 3 = 5$。
- 兔子 3 跳到 $4 - 5 = -1$。
### 样例解释 2
如果每只兔子的跳跃方式如下,可以获得最大不同坐标数 $4$。
- 兔子 1 跳到 $2 - 1 = 1$。
- 兔子 2 跳到 $3 + 2 = 5$。
- 兔子 3 跳到 $6 + 1 = 7$。
- 兔子 4 跳到 $5 + 2 = 7$。
- 兔子 5 跳到 $4 - 3 = 1$。
- 兔子 6 跳到 $4 - 1 = 3$。
### 数据范围
- $1 \leq N \leq 2 \times 10^5$
- $-10^9 \leq X_i \leq 10^9$
- $1 \leq R_i \leq 10^9$
- 所有输入均为整数。
由 ChatGPT 5 翻译