/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 575 点
問題文
数直線上に 1 体のタコ型ロボットと N 個の宝があります。
i (1\leq i\leq N) 個目の宝はそれぞれ座標 X_i にあります。
タコ型ロボットは 1 つの頭と N 本の足を持っており、i 本目の足の長さは L_i (1\leq i\leq N) です。
タコ型ロボットが次のようにして N 個の宝すべてを掴む事ができるような整数 k の個数を求めてください。
- 頭を座標 k におく。
- i=1,2,\ldots,N の順に、「頭から距離 L_i 以下の範囲、すなわち k-L_i\leq x\leq k+L_i をみたす座標 x にまだ掴んでいない宝が存在する場合、そのうちの 1 つを選んで掴む」ことを繰り返す。
制約
- 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}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X_1 X_2 \ldots X_N L_1 L_2 \ldots L_N
出力
問題文の条件をみたす整数 k の個数を出力せよ。
入力例 1
3 -6 0 7 3 5 10
出力例 1
6
k=-3,-2,-1,2,3,4 が条件をみたします。例えば、k=-3 のときは、次のようにして 3 個の宝をすべて掴む事ができます。
- 1 本目の足は -6\leq x\leq 0 にある宝を掴む事ができる。このうち座標 -6 にある 1 個目の宝を掴む。
- 2 本目の足は -8\leq x\leq 2 にある宝を掴む事ができる。このうち座標 0 にある 2 個目の宝を掴む。
- 3 本目の足は -13\leq x\leq 7 にある宝を掴む事ができる。このうち座標 7 にある 3 個目の宝を掴む。
入力例 2
1 0 1000000000000000000
出力例 2
2000000000000000001
-10^{18} 以上 10^{18} 以下のすべての整数が k として条件をみたします。
入力例 3
2 -100 100 1 1
出力例 3
0
条件をみたす k は存在しません。
Score : 575 points
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.