/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
長さ N の正整数列 A と正整数 K が与えられます。
数列 A に対して、以下の操作を何回でも行うことができます。
- 1 以上 N 以下の整数 i を一つ選び、A_i に K を足す。
\max(A)-\min(A) としてあり得る値の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを 1 行で出力せよ。
入力例 1
3 10 3 21 9
出力例 1
4
まず、i=1 を選ぶと数列は A=(13,21,9) になります。
次に、i=3 を選ぶと数列は A=(13,21,19) になります。
次に、i=1 を選ぶと数列は A=(23,21,19) になります。
このとき、\max(A)-\min(A)=23-19=4 となります。
\max(A)-\min(A) を 3 以下にすることはできないので、答えは 4 です。
入力例 2
5 6 4 100 5 10 450
出力例 2
2
Score : 400 points
Problem Statement
You are given a sequence A of N positive integers and a positive integer K.
You can perform the following operation on the sequence A any number of times.
- Choose an integer i with 1 \leq i \leq N, and add K to A_i.
Find the minimum possible value of \max(A) - \min(A).
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Output the answer on a single line.
Sample Input 1
3 10 3 21 9
Sample Output 1
4
First, choosing i=1 makes the sequence A=(13,21,9).
Next, choosing i=3 makes the sequence A=(13,21,19).
Next, choosing i=1 makes the sequence A=(23,21,19).
At this point, \max(A)-\min(A)=23-19=4.
It is impossible to make \max(A)-\min(A) at most 3, so the answer is 4.
Sample Input 2
5 6 4 100 5 10 450
Sample Output 2
2