← 返回题目列表

AtCoder · abc434_e

E. 分发兔子

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 兔子编号 数轴上的 1 to N 。兔子 i 位于坐标处 X_i。多只兔子可能位于同一坐标。
每只兔子都有一个参数,称为 跳跃力和兔子 i 具有跳跃力 R_i.
现在,所有兔子都会跳一次。当兔子到达坐标时 x 具有跳跃力 r 跳跃,移动到坐标 x+r 或坐标 x-r.
如果你可以自由选择每只兔子跳到哪个坐标,请找出所有兔子都跳完后,兔子所在的不同坐标的最大可能数量。

约束

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq X_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
X_1 R_1
X_2 R_2
\vdots
X_N R_N

输出

输出兔子跳跃后出现的不同坐标的最大可能数量。


示例输入 1

3
4 1
2 3
4 5

示例输出 1

3

如果每只兔子如下图所示移动,就有可能实现 3 作为兔子跳跃后出现的不同坐标的数量,这是可能的最大值。

  • 兔子 1 移至 4 - 1 = 3.
  • 兔子 2 移至 2 + 3 = 5.
  • 兔子 3 移至 4 - 5 = -1.

示例输入 2

6
2 1
3 2
6 1
5 2
4 3
4 1

示例输出 2

4

如果每只兔子如下图所示移动,就有可能实现 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.

示例输入 3

10
1000000000 1000000000
1000000000 1
-1000000000 1000000000
-1000000000 1
0 1
2 1
1 2
4 1
3 2
4 3

示例输出 3

9