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 翻译