| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 216 | 100 | 91 | 47.644% |
President K is taking on the role of adjusting the room temperature of the officers’ room. He wants to make the officers as comfortable as possible.
Now there are $N$ officers in the room. Each officer is numbered from 1ドル$ to $N,ドル and the appropriate temperature for officers $i$ (1ドル ≤ i ≤ N$) is $A_i$ degrees when (s)he is not wearing jackets. For each officer, the appropriate temperature drops by $T$ degrees every time (s)he wears a jacket. In other words, when the officer $i$ is wearing $k$ jackets, her/his appropriate temperature is $A_i − kT$ degrees.
When the room temperature is $x$ degrees and the appropriate temperature of a certain officer is $y$ degrees, the discomfort index of the officer is expressed as $|x − y|$. Note that $|t|$ represents the absolute value of $t$. Each officer wears the appropriate number of jackets of 0ドル$ or more to minimize discomfort index, depending on the room temperature.
Here, president K decided to call the maximum discomfort index among all officers as room’s unpleasantness, and set the room temperature so that the room’s unpleasantness was minimized. Note that the room temperature must be an integer.
Write a program which, given information about the officers and the appropriate temperature, calculates the minimum room’s unpleasantness.
Read the following data from the standard input.
$N$ $T$
$A_1$ $A_2$ $\cdots$ $A_N$
Write one line to the standard output. The output should contain the minimum room’s unpleasantness.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 15 | $N = 2$. |
| 2 | 5 | $N ≤ 3,円 000,ドル $T = 1$. |
| 3 | 30 | $N ≤ 3,円 000,ドル $T ≤ 2$. |
| 4 | 35 | $N ≤ 3,円 000,ドル $T ≤ 3,円 000$. |
| 5 | 15 | No additional constraints. |
2 4 19 24
1
For example, if the room temperature is set to 16ドル$ degrees, the appropriate temperature for officer 1ドル$ will be 15ドル$ degrees by wearing one jacket; the discomfort index is $|16 - 15| = 1$. The appropriate temperature for officer 2ドル$ will be 16ドル$ degrees by wearing two jackets; the discomfort index is $|16 - 16| = 0$. At this time, the room’s unpleasantness becomes 1ドル$.
Since the room’s unpleasantness cannot be made smaller than 1ドル,ドル output 1ドル$.
This sample input satisfies the constraints of Subtasks 1, 4, 5.
3 1 21 19 23
0
For example, if the room temperature is set to 19ドル$ degrees, the room’s unpleasantness becomes 0ドル$. Output 0ドル$.
This sample input satisfies the constraints of Subtasks 2, 3, 4, 5.
6 8 24 22 21 25 29 17
2
For example, if the room temperature is set to 15ドル$ degrees, the room’s unpleasantness becomes 2ドル$. Since the room’s unpleasantness cannot be made smaller than 2ドル,ドル output 2ドル$.
This sample input satisfies the constraints of Subtasks 4, 5.