/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
正整数列 A = (A_1, A_2, \ldots, A_N) および正整数 X が与えられます。あなたはこの数列に対して、次の操作を何度でも行うことができます（0 回でもよい）：
- 添字 i （1\leq i\leq N）および、0\leq x\leq X となる非負整数 x を選ぶ。A_i を 2A_i+x に変更する。
操作結果の \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} としてありうる最小値を求めてください。
制約
- 2\leq N\leq 10^5
- 1\leq X\leq 10^9
- 1\leq A_i\leq 10^9
入力
入力は以下の形式で標準入力から与えられます。
N X A_1 A_2 \ldots A_N
出力
操作結果の \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} としてありうる最小値を出力してください。
入力例 1
4 2 5 8 12 20
出力例 1
6
A_i を 2A_i+x に変更する操作を (i, x) と表すことにします。最適な操作列の一例は次の通りです。
- (1,0), (1,1), (2,2), (3,0)
操作結果は A = (21, 18, 24, 20) となり、\max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 6 が達成できます。
入力例 2
4 5 24 25 26 27
出力例 2
0
最適な操作列の一例は次の通りです。
- (1,5), (1,5), (2,5), (2,1), (3,2), (3,3), (4,0), (4,3)
操作結果は A = (111,111,111,111) となり、\max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 0 が達成できます。
入力例 3
4 1 24 25 26 27
出力例 3
3
一度も操作を行わないことにより、\max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 3 が達成できます。
入力例 4
10 5 39 23 3 7 16 19 40 16 33 6
出力例 4
13
Score : 700 points
Problem Statement
You are given a sequence A = (A_1, A_2, \ldots, A_N) of positive integers and a positive integer X. You can perform the operation below any number of times, possibly zero:
- Choose an index i (1\leq i\leq N) and a non-negative integer x such that 0\leq x\leq X. Change A_i to 2A_i+x.
Find the smallest possible value of \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} after your operations.
Constraints
- 2\leq N\leq 10^5
- 1\leq X\leq 10^9
- 1\leq A_i\leq 10^9
Input
Input is given from Standard Input in the following format:
N X A_1 A_2 \ldots A_N
Output
Print the smallest possible value of \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} after your operations.
Sample Input 1
4 2 5 8 12 20
Sample Output 1
6
Let (i, x) denote an operation that changes A_i to 2A_i+x. An optimal sequence of operations is
- (1,0), (1,1), (2,2), (3,0)
which yields A = (21, 18, 24, 20), achieving \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 6.
Sample Input 2
4 5 24 25 26 27
Sample Output 2
0
An optimal sequence of operations is
- (1,5), (1,5), (2,5), (2,1), (3,2), (3,3), (4,0), (4,3)
which yields A = (111,111,111,111), achieving \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 0.
Sample Input 3
4 1 24 25 26 27
Sample Output 3
3
Performing no operations achieves \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 3.
Sample Input 4
10 5 39 23 3 7 16 19 40 16 33 6
Sample Output 4
13